Pathfinding – Hide and Seek Game
Posted in School, Software on July 5th, 2011 by Jamie – Be the first to commentIntro
For the last assignment for CIS564, we created a simple tag/hide-and-seek game using path-finding, and the behavioral steering from the last assignment.
A*
A* (A-star) is a path-finding algorithm which finds an optimal path between two nodes given a cost function which yields the distance from the start and a good heuristic estimating the distance to the goal. The game field is divided into a grid of 1600 squares. Each square is marked as open or obstructed, based on the presence of a mushroom obstacle. Obstacles may be placed dynamically by holding ALT and LEFT-clicking with the mouse. In Path-finding mode, Lenguins will plan a path around the mushrooms to the target.
Mushroom obstacle
The algorithm was implemented in C++ and compiled in XCode to a OSX Bundle for use with Unity. I turned out to be the only one to work on OSX. Since a Visual Studio project was required, I ported the code over to Windows after I was sure it worked. I’ve noticed interesting differences in the way the code works in OSX versus Windows–or it could be a difference in compilation between XCode and Visual Studio. For example, I was using a route where I subsampled a list of vectors that represented an agent path. I had something like:
std::list<vec3>& Environment::subsamplePath(std::list<vec3>& path, int factor) {
int i = 0;
for(std::list<vec3>::iterator it = path.begin(); it != path.end(); ++it) {
if(i % factor == 0) {
path.remove(*it);
}
i++;
}
return path;
}
This seemed to work fine on OSX, but Windows threw a fit. Unity would immediately crash when I ran the game. I traced the problem to this function and a little investigation shed some light on the matter. When you call remove, it invalidates the iterator–makes sense. So I changed the code to the following:
std::list<vec3>& Environment::subsamplePath(std::list<vec3>& path, int factor) {
int i = 0;
for(std::list<vec3>::iterator it = path.begin(); it != path.end(); ) {
if(i % factor == 0) {
it = path.erase(it);
}
else {
++it;
}
i++;
}
return path;
}
Freeze Tag
Clicking the “Hide & Seek” button will enable the Freeze Tag mode.
Game Options
You control a player and may select various camera control schemes.
Camera Modes
The AI-controlled Lenguin agents head towards various hiding spots placed on the map. New hiding spots may be placed using SHIFT + LEFT-click. They appear as blue spots on the map. Each Lenguin will head towards the nearest hiding spot. Once a Lenguin reaches a hiding spot, it will claim that spot, and other Lenguins which were seeking that spot will acquire a new target. The process repeats while there are empty hiding spots.
When the player comes into an agent’s line of sight, the agent will flee away from it. If the player is able to tag the agent, it freezes in place.
Frozen Lenguin
Non-frozen Lenguin agents will attempt to tag the closest frozen agent. If the tag happens, the Lenguin is unfrozen. The game ends when the player freezes all the agents. Then, the game restarts and play continues.
Game Field
Demo Video
Downloads
- Source – will be available someday, when I am done the program
- OSX Universal (13.1 MB)
- Win 32-bit (3.1 MB)
Progress Log
Here’s a progress log that I started but neglected to finish:
- Started work on A* algorithm 20100625 10:00 AM.
- A* code written but untested 1:00 PM.
- Difficulties debugging. An hour lost trying to setup some sort of debugging via Igloo. 3:00 PM.
- Formal debugging abandoned. A* code rewritten to be more clear using a AStarNode class 6:00 PM
- Started to test A* code with new class approach 6:00 PM
- Debugging slow and awkward. Results written to file. 8:00 PM
- Code finally works without sigaborts by eliminating pointer issues. More debugging. Logs seem to be increasing exponentially for some reason. 10:00 PM
- Debugging problem fixed. Stringstream used for debugging was not cleared each time it was used, resulting in exponential increase in log size. Lenguins move but in wrong direction. 11:30 PM
- In a stroke of insight, I try reversing the condition used in the priority queue (the A* open list). Things magically work after that. 20110626 12:30 AM
- More testing, creation of mazes, videos, showing path finding. Implemented code sent by TA to prevent agents stuck on obstacles. 2:00 AM
- Work started on camera and player actions 12:30 PM
- Issue with third-person control resolved by raising player slightly above map. Issue with camera enabling resolves player control with perspective camera. Mario-style camera hooked up to player. 2:15 PM
- Got freeze behavior working along with some game mechanics. There are some issues with collisions. 3:45 PM
- And then I stopped keeping track…
