The Daily Click ::. Downloads ::. Engine ::. Node Pathfinding in MMF
 

Node Pathfinding in MMF
Author: Pixelthief Submitted: 3rd August, 2008 Favourites:0
Genre: Engine Downloads: 880
Rated:


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 )



Posted by Pixelthief 3rd August, 2008

Oh and the .exe contains the open sourced MMF1.5 file, a stand-alone compiled version, and the extensions you need to open the open source one
 
Posted by AndyUK 4th August, 2008

I thought you were a TGF only man?
works pretty well, but if you change the target or player mid movement it wont work out a new path and just go through walls.
 
Posted by Pixelthief 4th August, 2008

well you could just replace the space bar event with the left/right click ones, so it triggers a new movement every time you change something
 
Posted by Assault Andy 5th August, 2008

That's a really nice example. Thank you!
 
Posted by Pixelthief 5th August, 2008

yarr it might not look like much if you tinker with it, but if you look at the source code you can see how easily adaptable it is into anything :~) I might write some with better algorithms or see if I can find any tricks with fast loops to allow full recursion, but both those are doubtful
 
Posted by Muz 9th August, 2008

Ouch, 290 lines (+comments) is quite long for just a pathfinding engine. I didn't actually read what the lines say, though
 
Posted by Pixelthief 10th August, 2008

well, the vast part of the code is just copy/pasted over again

the loop is pretty simple, its just that MMF doesn't do recursion, so instead of calling "Loop" again, it has "Loop1" call "Loop2", etc, even though the code is the same.
 
Posted by Pixelthief 12th August, 2008

nvm MMF does do recursion, and this can be adapted to full recursion in like 10 seconds.
 

 



Author

Favourite



Advertisement

Worth A Click