A while back I was helping out on some AI for the game civil. I had a working A* path finding algorithm and most of a simple influence map before I ran out of free time. I've taken that work, decoupled it from the civil code and packaged it up here in case others would find it useful in some way.
Python A*
This A* implementation was built for a hex based map, but I tried to keep it generally applicable to a number of maps and have included the distance cost algorithms for 5 different map layouts (both grid and hex). The package includes C implementations of the distance cost functions and the distutils setup files to compile them.
There are a few other Python A* implementations that I know about. One is by Peter Norvig included in his AIMA Python code in support of his (IMO) very good AI textbook (I still have mine) AI: A Modern Approach.
Another python A*, quite fast according to the author Ivo Danihelka. See the shortPath() function. Here's a pygame thread on path finding where a good number of other python A* implementations are referenced.
Python Influence Map
For a good overview of influence maps read the article on a simple board game ai from generation5 or for more details you can read the newsgroup discussion on gameai.com or my local copy.
The influence map is still something of a work in progress. It uses Numeric and is fairly fast and includes a good bit of documentation in the source. If not usable out of the box, it should at least provide an interesting launching point as the Numeric code was a bit tricky to get right.
- influence_map.tar.gz
- influence_map.zip
- newsgroup influence map discussion [from gameai.com]
- newsgroup strategy ai discussion [from gameai.com]
Python/C Heap
Note that Python 2.4 now comes with a C implementation of heapq making this redundant.
I needed a fast priority queue algorithm and had been using the pqueue module. But this module was never well suited for the A* being based on a Fibonacci heap. It also doesn't seem to be to actively maintained (its part of an old project for the author), wasn't widely distributed and I have no wish to adopt it (Fibonacci heaps are overly complicated). So I hunted around for a replacement. I tried the couple of python versions I can across [1] but was unhappy with their performance. The best of the two was the standard heapq.py module. It was easy to understand and I liked the fact that I could use the standard library as a fall back. So I reimplemented it in C. It works just like the pure python one but is nearly 20 times faster.
- Just the C source.
- heapq.c
- I finally got around to making some disutils source packages. :)
- heapqc.tar.bz2
heapqc.zip
[1] 2 implementations in ASPN's python cookbook. and the heapq.py module in python 2.3+.
