pygame is
Python
Simple DirectMedia Layer
 
 
pygame.org is
Site Swing
Path Finding

Path Finding - 0.1.0

Xueqiao Xu (qiao)

Tags:

Description

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)

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

Links

Home Page: http://code.google.com/p/mycodeplayground/
Source: http://mycodeplayground.googlecode.com/files/pathfinding-0.1.0-src.tar.gz
Windows: http://mycodeplayground.googlecode.com/files/pathfinding-0.1.0-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
spotlight

 
our projects
pygame.org welcomes all python game, art, music, sound, video and multimedia projects. If they use pygame or not.
 
recent releases
Oct 21, 2014


Oct 20, 2014

Oct 16, 2014

Oct 9, 2014

Oct 8, 2014

Oct 7, 2014

Oct 4, 2014

Oct 1, 2014

Sep 19, 2014

Sep 17, 2014

Sep 9, 2014

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