Hi Everyone. I'm designing and programming a top down shooter in Python. I'm quite new to pathfinding and complicated AI in general and I'm having problems with pathfinding affecting my game's performance. I have written what I believe to be a relatively efficient A* derived pathfinding algorithm. It can find the shortest path on an 100*100 grid with random weights in less than 0.12 seconds reliably. The way I have my world implemented is that the world has a list of game objects, and each game object has an x and y coordinate which are doubles. Right now, I've also created a pathfinding grid to "layer" on top of the world. The grid is separated into squares that are each the size of my smallest character sprite. My pathfinding algorithm checks if there is an obstruction in a square to determine the weight of the square (This is done while loading the level and not in real time). The current grid size I am using for my world is 48*56. I run the pathfinding algorithm for each enemy every half second if and only if their destination has changed. However, I am still noticing a relatively big drop in performance. Every two enemies added drops my fps in game by about 1. This is certainly caused by my pathfinding as rendering them and making them move without pathfinding does not drop my performance. Considering that I'd like to be able to have a peak of around 30 different pathfinding entities in the game at a time, this will really hurt my game's performance. So I was wondering, what should I be doing to pathfind more efficiently? Is my algorithm too slow, is Python too slow, or is there some game design tricks I can use to speed things up?

Thanks for your time,

Jason Wolter

You mean .12 seconds for one entity? Even if it's python, that's not efficient my man. People have had larger grids with less time. Can you show us the code for your pathfinding? We need the data structure as well.

Now if you have all entities pathfinding at once, that's your second problem. Typically pathfinding has been known for being expesnive, and having an arbitrarily large set of nodes will make performance worse. There's a number of tricks that goes into optimizing it... but mind you that A* has never been known for being fast. As popular as it is, you might not always want a shortest path.

I'm going to withold mentioning those optimizations till we get a look at your code.

Does your top down shooter have a lot of complicated obstacles, like corridors? Do you need pathfinding, or would doing some steering serve you better? Also, depending on your entities and their sizes, going with the smallest may not be the best way, you may want to go with the most common size for your grid, and your smaller entities would just use that same grid. (or if you have gobs of memory, you could have separate grids per entity, but I'd hold off on that)

Sounds like the cost of your routine is higher than I would expect. It is worth looking at your open/close lists, how they are managed and stored. Are you rebuilding the lists constantly? Is there a bug in the heuristics calculations? etc

Thanks for all your feed back so far!

I seem to be having a hard time getting indentation working properly in this post editor, so I attached my A* search code as a .txt file to this forum post: [attachment=32252:astar.txt]

Steering also looks promising, but I would like to have a pretty wide variation of types of levels, from wide open boss arenas, to small and tight corridors. Right now I'm just trying to get a "zombie" like enemy (One that simply moves to the player's location) Pathfinding through a complex level without running into things, but I'd like to be able to eventually implement more complicated AI "personalities" such as enemies that try to run from the player when they're in trouble or enemies that try to specifically attack from behind the player. I feel like I will need a fleshed out pathfinding algorithm for this, but I'm somewhat new to game development so I could certainly be wrong.

I've done a couple of real time games with very limited AI before and quite a few turn based games with more complex A.I. (chess, for example), but if any of this seems too ambitious for my level, let me know if there is somewhere else I should start. I'm doing this for fun and my own learning, so there's no urgency to it.

EDIT: The version of Python I'm using is 2.7.11. There is a library I'm using for another part of the game that has not yet been updated to be compatible with Python 3. Additionally, one optimization feature I'm using right now which isn't apparent in the code that I uploaded is that I am checking if there is a straight line from the start to the goal before running the A* search and I am forgoing the search if I discover that there is one.

1. Do you use obstacles?

self.obstacles = []
return loc not in self.obstacles

Walks over every entry in the list, which is deadly for more than 2-3 obstacles. Use a set.

2.

if next not in totalCost or newCost < totalCost[next]:

Queries 'next' twice from totalCost, use 'get':

tc = totalCost.get(next)
if tc is None or newCost < tc:

3.

x = loc[0]
y = loc[1]

You can combine this

x, y = loc

4. This should not be needed I think, as you always expand in all directions

if (x + y) % 2 == 0: adjacent.reverse()

adjacent = filter(self.inGrid, adjacent)

Is a bit expensive, you also test 'x', and 'y', for 50% of the time, while you are only worried about 'x+1' etc.

5.

class PriorityQueue:

Needs "(object)" as base class, in Python 2.

Code layout is done by pasting code in the editor, selecting it, and then press the 'code' button, the "<>" icon. However, as you can see in my post, it fails to understand empty lines too :( (fixed by adding numbers in an edit)

What I think kills the performance is your movement directions. You only move horizontal and vertical. So if you must move 5 up and 4 right, the entire 5x4 area gives you feasible paths, so you have 20 locations in the costs rather than 9 (5+4).

I don't know the solution at this time, and I don't have the time now to think about it.

One thing you can do is check my hypothesis, by trying to move in some diagonal direction, and check the locations in your closed list afterwards.

Apart from the suggestions above, there's nothing obviously wrong there. The step you should take is to profile the code. That might be as simple as:

import cProfile
cProfile.run('whatever()')?

Better still, have it output to a file and view it in RunSnakeRun.

If, for some reason, you can't profile your code, put a timer around the code to measure how long it takes. eg.

start = time.time()
# ... call my code here...
elapsed = time.time() - start
print "Time elapsed: %2.3f" % (elapsed)

And you can extend that to measure sections of the code.

But trying to estimate efficiency based on FPS is very imprecise and misleading. (e.g. A decrease from 100fps to 50fps is potentially the same as the decrease from 20fps to 16.6fps - both indicating an extra 10ms per frame.)