There’s a really big set of resources here:
http://www-cs-students.stanford.edu/~amitp/gameprog.html
If you’re just starting out with pathfinding it should cover nearly everything you need to know. Not many tutorials cover the basics of building a graph though, so here’s how to build a very basic unoptimized graph:
If you want to build a graph you need to think about what the nodes are going to be. In my A* algorithm I tried both classes and dictionaries as nodes.
Dictionary is probably the easiest to work with when starting out:
node = {"xy_id":[],
"g":0,
"h":1000,
"next_to":[],
"parent":None}
Each node has some attributes. Firstly its [x,y] position in 2d space, this is important because it can be used to identify the position in space of the node at any time. The next two-
- G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there.
- H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don’t know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.).
-are calculated when running your A* algorithm. You can find out more about them in the tutorial.
The next to parameter is the most important bit, this is what changes the graph in to a real graph, without it, you’ve just got a bunch of co-ordinates. The next to list is a list of all the node’s valid neighbors. If you can travel to another node directly from this one, it should go in here.
Parent is used last of all. When doing your A* algorithm you’ll be finding the best square from the list of neighbors. When you’ve got it you can set it’s parent as this node. There are times when you want to change the parent, like when checking if there is a better way to get to this square by going diagonally. When you’ve finished the search and every node in the closed list has been checked you go back from the end square getting the parent of each node above it and making a list of nodes to be followed.
When building a graph you can make a graph class, or a graph dictionary. Dictionary is probably the easiest at first.
just start with:
graph = {}
Then go through the verts in your walk mesh and run a function to create a blank node and put it in the dictionary.
I use a key derived from the xy co-ordinates so I can look up the dictionary entry easily:
key = str(x) + "$" +str(y)
If I later want to break this down to get the co-ordinates from the string I can use the string.split(“$”) operation from python.
Good luck, it took me months to understand pathfinding and I still don’t know well about the various optimizations.
Here are some hints which will save you a lot of time:
- You have to rebuild your graph every time you run the A*. You can’t reuse an existing graph unless you go through and reset every node. It’s faster just to rebuild the graph. Also things might change in your game, like doors being open and such, so you have to rebuild it anyway.
- You don’t have to add every single vert to your graph. At most you need a rectangle around your start and finish locations with a border of about 10 squares to cover the possibility of back tracking. Cropping your graph like this will increase the speed a lot, especially when dealing with movement across a small distance.
- Investigate other pathfinding options. A simple ray casting check from A to B before running A* will tell you if you can walk to the target without calculating a complex path. If so, you don’t need to run A* and you just saved a huge amount of processing time.
- Find a way of visualizing the various elements returned by your A* algorithm. I use a simple script to place and erase colored cubes to show the route, open and closed lists. This will help you to know where you’re going wrong in real time as you run the pathfinder.
Here’s an example of that in action:
You can use something like this:
def icons_clear(property,scene):
ob_list = scene.objects
for ob in ob_list:
if ob.get(prop,False):
ob.endObject()
To clear away the last result and then:
def debug_path_lists(own,a_star,scene):
if a_star["path"] != []:
for sq in a_star["path"]:
tile = sq.split("$")
pos = [int(tile[0]),int(tile[1]),0.1]
tile = scene.addObject("node_green",own,0)
tile.worldPosition = pos
if a_star["open_list"] != []:
for sq in a_star["open_list"]:
tile = sq.split("$")
pos = [int(tile[0]),int(tile[1]),0.1]
tile = scene.addObject("node_blue",own,0)
tile.worldPosition = pos
if a_star["closed_list"] !=[]:
for sq in a_star["closed_list"]:
tile = sq.split("$")
pos = [int(tile[0]),int(tile[1]),0.1]
tile = scene.addObject("node_red",own,0)
tile.worldPosition = pos
To place cubes representing the A* path, open list and closed list.