This is a (relatively) simple pathfinding approach for MMF that I cooked up last night to use in my game for Peblo's competition, but I thought I'd post it open source right now so people can see what makes it tick so to speak. It uses an extremely simple ball-movement type, but directs the AI towards pre-defined nodes on the map.
In order to find the correct path through these nodes, the AI employs Depth-First-Search through the tree of interrelated nodes. Anyone whos taken an IT class already knows what this means, but for the rest, please read this:
http://en.wikipedia.org/wiki/Depth-first_search
Left Click: Place the Player
Right Click: Place the Target
Space Bar: Start!
Enter: Toggle Node Visibility
Basically, the algorithm works like this:
Given two X/Y positions, the PLAYER & the TARGET.
1: Find the closest node to the PLAYER, ignoring any that do not have a direct line of sight. Mark this as the START
2: Find the closest node to the TARGET, ignoring any that do not have a direct line of sight. Mark this as the FINISH
3: Employ a Depth-First-Search starting at the START and ending at the FINISH. Weight each step by going to the next node that is CLOSEST to the target.
4: Return the list of nodes to the PLAYER
5: Check to see if the PLAYER has a direct line of sight to the 2nd node; if so, throw out the first node (prevents AI from backtracking needlessly)
6: Have PLAYER move from node to node in order
7: While moving from nodes, check if PLAYER has direct line of sight to TARGET, if so, erase node-list
8: Once node-list is empty, proceed directly to TARGET
In its current shape, this isn't practical for games. You need to A: give your enemy an actual movement instead of using the built in ones, and B: flesh out some bugs. Because the detector is big, if the enemy is against a wall it will say every node has an obstactle inbetween and throw it out, so that should be switched to individual pixel checking instead of using an active for collisions. Also, if there is no node in the immediate line of sight, the enemy simply won't be able to move. So you'll need to cover your map pretty throughourly. Also, because MMF can't do recursion, the tree is obviously limited to a depth of 8 (look at how I did it in the code). This means that after going 8 nodes, even if its completely the wrong direction, the enemy will take that path regardless. You can just copy/paste and edit the depth X groups to bump this up a notch, but run time performance might be affected. I think it really depends on how many nodes you'll have. The more searchs you do, the less likely the path will lead the wrong way.
Also, because this is a depth-first search employing an extremely simple greedy algorithm, it will NOT always give the shortest path. Given uncapped recursions it will ALWAYS reach the target, but it could easily go across the entire map and return to get to the location 30 pixels away. The more interconnected nodes you have, the less likely this is.
 Review This Download
http://claniraq.googlepages.com/TreeSearch.zip (331.44 kb )
|
Other Creations
Favourite