New misc file: pathfinding

Decided that I’m going to go with “collaborative diffusion” pathfinding–I created a test file that implements this system of path finding quickly and easily.

Well, somewhat. The current file set I’ve got up there calculates a path from the bottom left of the screen to the middle 30 times, and it takes ~.43 seconds on my machine to do that. I’m going overly generous in terms of the depth parameter–reducing that cuts the time down significantly–and my AI won’t need the full path to the target anyway using this method, so in terms of processing time I don’t think it’ll be an issue. Dijkstra’s algorithm would’ve been nice, as would A*, with the latter I hear being the fastest, but I think with some playing I can get what I’ve got now to suit my needs.

*Oh, and I discovered switching to numpy was about as simple as doing find/replace on all “Numeric” entries with “numpy”. Heh.

Some more testing shows that the floodfill part of this is the most expensive part of the algorithm. Should’ve been obvious actually, but, eh.

Advertisements

2 Responses to “New misc file: pathfinding”

  1. Benedict Says:

    If you are looking for a python A* pathfinder that would take about 30 min to hook into your project (thats how long it took me), check out: http://eli.thegreenplace.net/

    I’m following the dev of Graff, and looking forward to playing it and reading the source sometime soon. 🙂

  2. davidthabomb Says:

    Your work is awesome. Its very usefull, please explain how you created the numpyarray… It would be awesome!


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: