Pathfinding in MMF Flash

Hello guys,

Say err... any idea of path finding in the MMF Flash? Seems the PathFinding Object doesn't work in mmf flash :(

Anyway (in a not so related question) ... how do we create extentions for the mmf flash? I have downloaded the SDK 60 and after reading the help files... I still have no idea.
Sorry I am just curious.

Thank you.

You need the Flash SDK which is not publicly available.

Oh.. errr... ok.. :(

Thanks for the info.

Anyway if anyone has done it in the MMF Flash please do tell me.

Thanks.

I just built one last night for MMF's flash. It was a great learning experience!

I'm not going to talk you through it, but basically I just read this and applied the theory to MMF's programming language.

It also helps to have a paper and pencil handy so you can play through the theory on paper to ensure you understand it fully.

If is sounds too daunting, then I suppose you can just wait for somebody to adapt the pathfinding object.

Thanks for the reference. Yes... it's kinda confusing but I will try again and again... just hope it's fast enough once I get it working :D

Thanks.

I might build you a graphical example to help out... also the wikipedia entry for Dijkstra's algorithm is very helpful. Especially this part:

Quote:

---

1.Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.

2.Mark all nodes as unvisited. Set initial node as current.

3.For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.

4.When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.

5.If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next "current node" and continue from step 3.

---

Nodes are just squares on a grid. Distance is likely to be 1 for each adjacent square apart, although diagonals may be greater than 1 as per geometry. If you wanted perfect accuracy you could get the true distance by using the distance formula, but 1 is usually sufficent for a square grid. Start with big grid spacing like 64x64 apart and then go for a smaller grid once you know it's working. Your grid could just be an array object, or it could be a bunch of active objects set out in a grid across your level. The array will be faster, but the active objects will give you a visual representation of the pathfinding at work.

Dijkstra's is a little slow as it finds the optimum route, A* is much faster.
(But on small enough grids you won't care)

Ryan,

Seems like the Dijkstra is easier to understand then the A* and to implement.
I found a nice simple article on A* here

http://www.policyalmanac.org/games/aStarTutorial.htm

but it does not explain too detail.

ChrisB,

Yup.. I did search around and found the same thing you said.. Dijkstra is slower than A*.
I guess if we want to make a game with huge maps then A* is preferable... while small fixed grid games can do with Dijkstra.

While... say.. games like those zombie homing in on the player with no obstacle in the way can do without any pathfinding :D

I figured if I count the A* on each zombie with obstacle, it will kill the processing power in flash :(

Thanks guys :D

If you're going to scatter a whole bunch of zombies through a level, perhaps you could just create a few key pointer nodes at areas in the level.

For example: if a zombie is going to chase you through twisted hallways, have a path of nodes through the hallways. If zombie collides with node 1 and cannot see the player with line of sight, walk towards node 2, if zombie collides with node 2, walk towards node 3, etc. etc.

That'll give the illusion of intelligent pathfinding without the cost of processing power.

Ok I almost got it... the A* thingy...

Here is the sample..

View MFA

Careful... it's not stable yet but basically I hope I am in the right direction.
Using arrays and string parsers...

Is this the right way? Or is there another?
Do comment... especially on the usage of the Loops... :(

You're definitely on the right track. Use of arrays and fastloops is good; having a visual representation will help you with debugging. The pathfinding I built uses Dijkstra’s algorithm so won't beable to comment on the efficiency of your code. My game works on a very small grid so as ChrisB said, speed is not going to matter so much.

How do I add obstacles to the grid? I can watch it draw a line towards the destination, but how do I make it maneuver around obstacles? There are currently no obstacles on the grid.

Sorry haven't implement any obstacle yet. Having some problem understanding how the concave obstacle works... just couldn't get it working right :(