AI Software Solutions

Here it is: A page with real solutions to various AI-related problems! Pathing algorithms, weapons allocators, bridging algorithms, etc. -- anything that some developer somewhere wants to share with his or her peers -- they're all here. Or soon will be (I hope).

Note that there are no warranties, expressed or implied, of course. Note too that there are many different approaches to any problem, and I'm not about to critique somebody's hard work just because he/she doesn't indent code way the Software Gods intended (three spaces, no tabs, in case you didn't know).

Public Plea: If you have code or code fragments that you'd like to contribute, please e-mail me. I'd love to put it here for all to use and learn from. And just because there's (for example) already an A* algorithm here doesn't mean we can't use your version; it just might be the slightly faster one that makes the next Command & Conquer possible. Don't think of it as giving away your secrets; think of it as exchanging ideas. That's what the Web is all about, after all! And besides, what your boss doesn't know won't hurt him, right?

Currently Available


Tom Grubb's Delphi-based Flocking Demo (with code)
Tom Grubb's Delphi-based Pathfinding Demo (with code)
Andrae Muys' Influence Mapping Demo (with code)
Aurel Balmosan's Random Terrain Generator (with code)
Steve Hodsdon's Influence Mapping Viewer (with code)
Bryan Stout's Pathing Algorithm Utility (link)
Tim Hardy's A* Implementation (with code)
Geert-Jan van Opdorp's Java A* Implementation (with code)
Amit J. Patel's A* Implementation (with code)
Neil Kirby's Terrain Generator (with code)
Richard Wesson's "Ant Races" Pathing Algorithm (psuedocode)


Tom Grubb's Delphi-based Flocking Demo (with code)

Thomas Grubb was semi-inspired by the first Game Programming Gems book and decided to put together his own flocking app. It's pretty nifty, written entirely in Delphi, and of course he's made source code available to anybody who's interested. The demo lets you do a few things mine in that book didn't--you can run or step through the sim, change the number of flocks, toggle a given flocking rule on/off, and influence the strength of the effect a given flocking rule has on the flock in question (this last is rather interesting). Nifty stuff, and worth a look.

Tom Grubb's Delphi-based Pathfinding Demo (with code)

Thomas Grubb has put together an interesting little A* application written entirely in Delphi. He says it was inspired by Bryan Stout's excellent A* article in the October/November, 1996 issue of Game Developer (which you can find here). It's not a bad implementation at all, and it's a bit easier to follow than some. If you don't already have your own pet A* algorithm, or if you just gotta see it in Delphi to understand it, this is a good place to start.

Andrae Muys' Influence Mapping Demo (with code)

AI researcher Andrae Muys has kindly provided a demo program which demonstrates the Influence Mapping (something discussed at length over in the archived Influence Mapping thread). It's pretty nifty. You can snag the source code here.

O Aurel Balmosan's Random Terrain Generator

comp.ai.games participant Aurel Balmosan has donated an interesting terrain generator based on suggestions originally made by Mr. Mandelbrot. I haven't compiled it myself (at the moment I don't need one, but someday I will) but all the code is there, as well as a writeup as to how it all works. Download the zipped file and see what you think.

O Steve Hodsdon's Influence Mapping Viewer

Steve Hodsdon is one of the "regulars" over on the excellent comp.ai.games newsgroup. He's whipped out a quick and dirty (but it works; that's what's important) utility that allows one to view Influence Mapping. It's pretty cool, and helps to understand the way IM works. You can download a zipped version of it, with source code, here.

O Bryan Stout's Pathing Algorithm Utility

Bryan Stout has recently written an excellent article on pathing for the October/November 1996 issue of Game Developer magazine. As a part of this article he provided (available for download from the afore-mentioned GD site) his graphical Pathing Algorithm Utility.

Bryan originally showed this utility at the 1996 Computer Game Developer's Conference, then spent some time revising it for the GD article. It's a fascinating tool that enables game developers to see for themselves how various pathing algorithms work, what happens when you tweak the algorithmic parameters, etc. Well worth your time to check out and study.

O Tim Hardy's A* Implementation

Tim Hardy is a developer who's fairly active on the comp.ai.games newsgroup. He's written an implementation of the classic A* pathing algorithm which he's generously offered up as the first item on this page. The algorithm is implemented in Visual C++ 2.2.

Tim's code is presented verbatim, as submitted to me. I have downloaded and compiled it, so I know that works. If you have any questions you should direct them to him. Any document formatting errors you should report to me.

Note: Eventually I'll add a download capability to this site; right now I'm not sure how this ISP handles that.

Hop over here to see Tim's code.

O Geert-Jan van Opdorp's Java A* Implementation

Geert-Jan van Opdorp has written a version of the A* algorithm that's entirely in Java--easily making it the single most interesting piece of Java code I've yet seen. Implemented to solve a tile-based puzzle game, he uses a hash table internally rather than the normal linked lists and/or priority queue. (By the way, for those who don't know, Java is a pointerless language for security reasons.)

Geert-Jan's code is presented verbatim, as presented on his page. He is toying with the idea of reworking the internals somewhat to take advantage of faster Java techniques which he has recently learned, and has promised an updated copy if he does so. If you have any questions you should direct them to him. Any document formatting errors should be reported to me.

Note: Eventually I'll add a download capability to this site; right now I'm not sure how this ISP handles that.

Hop over here to see Geert-Jan's code.

O Amit J. Patel's A* Implementation

Amit J. Patel has provided a concise, tight version of the A* algorithm which is specifically geared towards hexagonal maps. One thing I particularly like about it is the methodology he uses to change the order in which adjacent tiles are examined (which helps to avoid pathing bias). This costs very little and yet can make much more "realistic" looking paths come out. Amit also uses a numerical heuristic which he can adjust in realtime depending on how much CPU time he has available, vs. an algorithmic heuristic.

Amit's code is presented verbatim, together with some comments he provided after sending me the code. Note that this version of his A* algorithm is an earlier, easier-to-understand version; Amit has a faster, more refined, but arguably more difficult to follow version over on his web page. If you have any comments or questions about the code itself, e-mail him. If you find formatting errors, please feel free to e-mail me.

Note: Eventually I'll add a download capability to this site; right now I'm not sure how this ISP handles that.

Hop over here to see Amit's code.

O Neil Kirby's Terrain Generator

Neil Kirby has attended the Computer Game Developer's Conference for several years now, and has given a number of papers and presentations. In conjunction with his 1991 paper he has provided a copy of the utility that he used to generate terrain. This utility is nicely done and could serve as a good "jumping off" point for others who want to do something similar.

If you have any comments or questions about the code itself, e-mail him. If you find formatting errors, please feel free to e-mail me.

Note: Eventually I'll add a download capability to this site; right now I'm not sure how this ISP handles that.

Hop over here to see Neil's terrain code.

O Richard Wesson's "Ant Races" Pathing Algorithm

Richard Wesson has been a regular on the comp.ai.games newsgroup for some time. He's implemented an interesting path-solving paradigm that uses ants running about the map as a conceptual model. From a pure theoretical aspect this makes it somewhat like Djikstra's Algorithm, though there are some differences.

Richard presents his approach in psuedo-code right here . If you have any comments or questions about the algorithm, just drop him a line. If you find formatting errors, please feel free to e-mail me.

---