Path Finding

Path Finding - 0.1.1

Xueqiao Xu (qiao)

Tags:

pathfinding astar algorithm bfs dijkstra

Description

This is a demo visualizing the execution of various path-finding algorithms

Curently five algorithms are included:

A* (using Manhattan distance)
A* (using Euclidean distance)
A* (using Chebyshev distance)
Dijkstra
Bi-Directional Breadth-First-Search

This is a Client/Server application. You should start the server first and then the client.
Also, you can start the server on one machine and run the client on a different machine, as long as the two machines are connected.

Requires Python 2.6+ (2.5 and 3.x is not supported)

video: http://www.youtube.com/watch?v=DINCL5cd_w0

Changes

Updates: version 0.1.1 Feb 17 2011
Add: If client fails to connect to the server, it will continuously attemp to connect every 5 seconds. Related notification is also added.
Add: Window icons.
Fix: Asynchat related message queue issue.
Fix: Working directory related issue.
Chg: Refactored some codes, and added more documents and comments.

Links

Home Page: http://code.google.com/p/mycodeplayground/
Source: http://mycodeplayground.googlecode.com/files/pathfinding-0.1.1-src.tar.gz
Windows: http://mycodeplayground.googlecode.com/files/pathfinding-0.1.1-win32-dist.zip

Screenshot

click to view original size

Releases

Path Finding - 0.1.1 - Feb 16, 2011
Path Finding - 0.1.0 - Feb 12, 2011

Pygame.org account Comments

If you wish to leave a comment with your pygame.org account, please sign in first.

February 16, 2011 10:59pm - Xueqiao Xu - nickname: (qiao)
@seeks I'm glad you like it. There's something that I would like to mention. The codes are written for demonstration, so I didn't spend much effort optimizing it. On a grid map of size 40 x 20 without much obstacles, my implementation of A* would usually spend less than 5ms. However, on a very complicated maze of the same size, it would spend around 50 - 70 ms, which means that it's nearly impossible to be applicable in a game which needs realtime pathfinding and meanwhile keeping a framerate of at least 30. And as for the reason for implementing it using a C/S model, it's simply because that I found network programming interesting and want to practice it :) It will surely be much simpler to get it working without a C/S model.
February 16, 2011 7:18pm - James Hendrie - nickname: (seeks)
This is some excellent work here. My brother and I are looking into making a game, and this seems like it could save me at least a couple weeks' worth of work. Probably more, as I'm not an especially talented programmer. Even so, I'm wondering why the need for a client/server model rather than just a pure client one. How difficult would it be to get this working without the server, or are there good reasons to keep the server running?
February 14, 2011 12:19pm - Xueqiao Xu - nickname: (qiao)
@pchasco Thanks for the comment. But the question is: the problematic thread and the corresponding message queue is handled automatically by asynchat, a standard library. The simplest solution would be using a modified copy of that module. I have examined its source and I'm quite sure that several lines of hack on asynchat (adding locks to make the access atomic, as you suggested) will work. However, I also think that this issue might be caused by my improper use of it. So, I'll still be checking around to find a more elegant solution.
February 14, 2011 10:16am - Patrick Chasco - nickname: (pchasco)
Even though the module may not be thread safe, you can synchronize access to the buffer using a threading.Lock object. http://docs.python.org/library/threading.html#lock-objects
February 13, 2011 8:37pm - Xueqiao Xu - nickname: (qiao)
Thanks for your feedback. I myself have also encountered this problem before. This problem is caused by the asyncore/asynchat module. When two threads are trying to get message from the FIFO simultaneously, such error will arise, since the module is not thread-safe. I'm still trying to fix this bug.
February 13, 2011 6:24pm - Robert Leachman - nickname: (quazar)
Good stuff. Sometimes it fails here with a stack like the following but repeated attempts do work: Unhandled exception in thread started by <bound method SecondaryServer._step of <__main__.SecondaryServer connected 127.0.0.1:64620 at 0x2d2f30>> Traceback (most recent call last): File "server.py", line 155, in _step self.push(data) File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/asynchat.py", line 186, in push self.initiate_send() File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/asynchat.py", line 244, in initiate_send del self.producer_fifo[0] IndexError: deque index out of range