Map Editor with A* Pathfinding and Networking
Excecutable (103Kb)
Abstract
This piece is a combination of a couple of courseworks and some work in my free time. The two Modules involved in uni were games tools programming and networking. In my own time I built into this an A* path finding algorithm that i wrote myself from scratch. Probably the easiest way to describe the whole program and its evolution is through the modules that brought it about.
First of all, in third year I took a module called "Games Tools Programming" in which I had to create a program that could parse scripts and do something with them. Those scripts had to be syntactically designed to be of use to a non-programmer too. My coursework essay for this component can be found here.
I set about creating a map editor that could read in a script which described a certain size grid of tiles with certain areas given a higher "cost" than other areas. These costs could later be interpreted by a path finding algorithm and rough or impassible terrain. In the screen shots below, the white areas have the lowest cost, green higher, blue even higher still and black are impassible areas or walls.
So I gave the program this ability to load in scripts and display them and also the ability to modify them by hand, using the mouse and some numpad keys. This map could then be saved as a .map file (basically a text file with a long string of numbers) and therefore be used in a game engine, which incidentally, it was.
For a third year group project, our group undertook the task of creating an RTS prototype. All RTSes involve some kind of map (usually a grid) and some kind of path finding algorithm for the AI agents to navigate that map. Perfect! This editor could be used for creating the maps. But what about the path finding?
Well before writing the path finding algorithm for the game engine, I tested it out on this program, since the game would ultimately use the same mechanics as the map editor; I could write it into this and then simply dump it right into the game engine, with little fuss. A little while later, after a lot of reading articles on the internet and a few seemingly "drunk" algorithms that randomly wandered off screen and crashed the program, I had a fully functional, fast and multi-threaded path finding algorithm that could surprisingly find its way around a complex maze in mere thousandths of a second. Plugged it into our game and bam, it worked.
The networking in the program really serves no purpose at all. Our coursework for the networking module in fourth year was to create a networked program. Wanting to avoid trying to write a game from scratch and then build networking into it, I thought I'd modify this program. It is now a hybrid server/client application so the user has the ability to become either a host or a client and have users connect and play on the same map. There is no game element in it, just a bunch of pacman ghouls running around path finding, but it does have dead reckoning in it and can support four connections at once, using both TCP and UDP for secure but fast networking code with the server side being multi-threaded. The essay describing this aspect in full can be found here.
