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.
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 ?
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.
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..
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.
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!
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!
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.
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.
[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!
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..
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!
Reply With Quote
(Dell has 1.6MHz) I think your algorithm will be a must..
