Thinking in graphs

So in my game, I added code to my cursor class so that it does a little bit more than move around and do nothing. I added some functions to trace the expected path that the character will take. However, I want it to act more intelligently rather than rely on the player to select each step. And there is this additional problem.

2018-07-25_1647

That’s right, I need to figure out how to maneuver around obstacles that the character shouldn’t be able to walk through. Pathfinding in general, is a topic that I don’t know very much about. And from initial research into the topic, I’ve learned that it requires that I view my map differently. Rather than just (x,y) coordinates, there is a mathematical concept called a graph which is used to model relationships between the locations. The terms used are nodes which represents locations and edges which are the connections/paths between the locations.

squares

Taking that information and translating it into code that actually does something is a bit overwhelming. So the first step for me is to take a square grid and figure out how to turn that into a graph. Here is my grid. The problem to solve is: Where are the connections?

Doing this in Unity is overkill for a problem like this and having to manage game objects seems like it would be distracting. So instead, I’m doing my research in Java.

The class ends up being simpler than I expected. Essentially all I need are an x and y variable that specify where they are and a list of objects of itself representing the different connections. Then I just add all the nodes to  a static list and build the connections with a for loop and similarly print by referencing the node from the static list.

So for instance this

</pre>
<pre>for(DemoGraph d : nodes)
        {
            d.addConnections();
            d.printConnections();
        }

Will output to 2018-07-25_1715


	

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s