pygame is
Simple DirectMedia Layer is
Site Swing
Path Finding

Path Finding - 0.1.0

Xueqiao Xu (qiao)



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

Curently five algorithms are included:

  1. A* (using Manhattan distance)
  2. A* (using Euclidean distance)
  3. A* (using Chebyshev distance)
  4. Dijkstra
  5. 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)



Home Page:


click to view original size


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

If you wish to leave a comment with your 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.
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 at 0x2d2f30>>
Traceback (most recent call last):
File "", line 155, in _step
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/", line 186, in push
File "/Library/Frameworks/Python.framework/Versions/2.6/lib/python2.6/", line 244, in initiate_send
del self.producer_fifo[0]
IndexError: deque index out of range

our projects welcomes all python game, art, music, sound, video and multimedia projects. If they use pygame or not.
recent releases
Nov 17, 2015

Nov 12, 2015

Nov 11, 2015

Nov 8, 2015

Oct 16, 2015

Oct 9, 2015

Sep 11, 2015

Sep 6, 2015

Aug 26, 2015

Aug 25, 2015

... more!
for pygame related questions, comments, and suggestions, please see help (lists, irc)