PathFinding In Flash - source included!

[sermad]

hey guys.

I bought the excellent - Isometric game programming with Direct X 7 yesterday and it had a chapter on pathfinding. anways...i ported the code to flash.

check

http://www.pointsinspace.com/pathfinding/

source is there too. feel free to optimize it!

sermad

[Mad-Sci]

Hey sermad, awesome .This realy made my day..

some stat..

P200MHz 128K RAM - no joy the script is running too slow
P300MHz 128K RAM - a bit of a joy
P800mhz 128K RAm - works all the way just a bit slow..

Having in mind that the above computers are old (Dell has 1.6MHz) I think your algorithm will be a must..
Have you tought to write a tutorial on that ?

Mad_sci

Q: why the first step is always in diagonal..

[Olorin]

Very nice... works well on an 8 by 8 grid... tried it on 25 by 25 and it nearly crashed my computer
One thing I noticed is that when you press "generate path" several times, with the same 'maze', you get different results.

Olorin

[Mad-Sci]

hahah Olorin I did try 50:50 tho 10:10 was ok with me..i think A+ is supposed to reevaluate the route each time well see the paths will be basicaly the same but mirror images..realy good code..

mad_Sci

[FlashCat]

Hay that is cool, nice work, sermad!

Duz that book you bought have any information on path finding in 3d games?

Hi Mad-Sci how have you bin?

Meow!

[Mad-Sci]

Cat wazup, dont see ya too often..how you doin..with me same old..its Friday so I dont complain..

mad_sci

[sermad]

cheers guys! I thought you lot might like it!

I've updated it for isometric. check

http://www.pointsinspace.com/pathfin...grid-astar.swf
http://www.pointsinspace.com/pathfin...grid-astar.fla

in answer to some questions :-

why does it pick a diagonal?

it doesnt! It picks a random square from the 3 available to it. Just click on generate path a few times and sometimes it will go straight or left or right! I need to put some sort of direction weighting there.

Why does it recalculate the path?

Well this is very useful especially if you are using something like this with a multiuser system <grin>. So an avatar could re check its path if some other avatar jumped in front of it.

The algorithm is very very clunky and I hope to get it faster so if anyone is good at optimizing code i would love to hear from you.

bada bing!

[FlashCat]

That’s good Mad!
Sorry I am not around much, but I am living threw HELL right know! I try to look at the board when I have the time and I am up for it.

So Sermad, I take it that book duz not have any thing in it for us 3D programmers, on path finding? I am working on a Tank game but my enemas are as dim as rocks, when it comes to utilizing the world around them!

I will take a look at your algorithm, I have some good tricks for 2D game programming, I will see what I can do!

Meow

[sermad]

no 3d pathfinding i'm afraid. Its really concerned with isometric systems. The book is good if you are into making stuff with Direct X too. Personally I do a lot of devving in C++ then port it back to Flash.

when you say 3d pathfinding you mean an x-y-z array?

if so then you add this to the current code but i would say it would be so slow to be useful! but im no expert in 3d or pathfinding for that matter!

[vinny_dog]

I think that pathfinding in Flash is an excellent idea in theory, but in practice??--Allow me to explain....When I tried to view your .swf, I got an error 3 times that a script is running that is causing the player to run too slowly. It just wouldn't work at all on my 433 AMD. I love the concept, but for practical uses, many viewers, such as myself, would be left out. Keep up the coding, though! I hope you the best.

[sermad]

aaah. but there is a way to do FAST pathfinding in FLASH!

You send the target location to the server and let the server do the pathfinding! then the server spits back the array!

By offloading all the calculations from slow old flash to fast old java and using xml sockets you get a good result. Trust me i've got it working!

[martin47]

How would you do the "thinking" on the server?

[sermad]

Originally posted by martin47
How would you do the "thinking" on the server?

well the server i use is based on java so i ported the pathfinding code to that(!) - as a function.

I created a new function which stores the Grid Array. Say Map[2][2] = "Blocked" and so on.

The server has listen handlers so when it receives at string with "GetPath" in it - it calls the pathfinding function. I could do this because I could extend the functions that the server has available. Because everytime an object move's the result is stored in the server side grid array, all I need to pass from client to server is - The Grid Pos the client wants to go to e.g. (4,5), The clients unique ID.

The server does it's stuff then spits back an array as an xml object to the client. Then the server updates its grid array and thats that.

The client is free'd from doing complex recursive math and doesn't need to store the entire grid with all the properties in memory, as if a square is blocked clientside - it is unclickable.

I hope that explains how I'm tackling this problem. I have no results on load testing or how long it takes to send/receive the path.

There are pro's and cons to either doing it client side or client/server. With the first the CPU is the limiting factor, with the second its CPU speed on the server (but this should be less of a problem) and Bandwith - If your client has to travel very far then you got a very long xml string back into flash and parsing that takes a long time! so it might take 3-4 seconds to get your path which could be unaccepteable.

I would love to hear anyones opinions on this.

yikes!

[Mad-Sci]

Q: how do you estimate the cost of each cell. Based on what ? distance only ...?

mad_sci

[sermad]

[QUOTE]Originally posted by Mad-Sci
[B]Q: how do you estimate the cost of each cell. Based on what ? distance only ...?

I'm not too sure if I can answer this correctly as I am really not too familiar with the code. But distance seems the main factor - but because the path found doesn't wall hug I was hazard in the blocked cell avoidance adds to the cost too...

Are you thinking about additional costs like terrain type or height? It not be too hard to add terrain in. From the iso book there is an excellent chapter on dynamic terrain creation with smoothing which I am just itching to do something interesting with.

sorry if this doesn't answer your question! very hard weekend. need sleep!

[Mad-Sci]

Ok here is what I have in mind...

1. each time you move you have 4 options up, down, left,right..
2. we can create a function wich will move the hero virtualy in all directions and will record the scores in array like node[x][y][score]. 3D Im taking about.
3. if there is collison with a wall the score will be increased with 10 points for example.
4. do let say 20 iterations in 4 directions at a time..
5. Buble sort the paths just sum up the node[score]
6. the end result will be simply go up,down,left,right for 20 steps and then reevaluate...

thus you will not use many MC as nodes rather virtual once..

mad_Sci

PS just on top of my head..

mad_Sci

[martin47]

I found this: The A* algorithm is explained here:
http://theory.stanford.edu/~amitp/Ga...arison.html#S1

[Mad-Sci]

mroe complex:

http://cpcug.org/user/scifair/Preygel/Preygel.html

mad-sci

[Mad-Sci]

so what you think guys which algorithm is best for Pac-Man for example...

mad-sci

[FlashCat]

Wo

I think we have over complicated maters. Random bounce path finding should be used in a real time game. it should influence one unit of movement per screen redraw then calculate a gen in the next frame and so on.

That is what makes it small and fast, but it will result in stupid moistures that can get stuck behind sum walls.

That’s why most games use 2 different path-finding algorithms for monsters.
1 that is small and works in most situations and a 2nd that is more robust for getting past the problematic areas.

Then all you need to do is toggle back and forth when needed, to save processing power!

By the way Sermad what is the name of that book?