I've been working on a few extensive top-down games, and I believe I've got the engine(code named 'gunnerman') pretty well constructed(for my purposes at least ). I've done alot with AI, including node based networks, squad based tactics, ect.
HOWEVER, I have put off pathfinding. The Open-Source posted is my original attempt, I recently opened up and adjusted some things(mainly terminology, actually). Before you laugh, this method is totally home-made. To me game-making *is* the game, so I didn't even bother searching google for pathfinding, I just tried to figure it out.
"Dijkstra's" algorithm sounds cool, so I plan to give it a shot.
In the meantime, for whatever benefit, here's my old one. I hope some people who are inexperienced can take a look(it's VERY heavily commented), and perhaps we can get some cool ideas, and maybe even work on something (thus the title "Open-Source").
For those that are the masters, you may give critical input of course
I will explain the details in a seperate post, the above was more to explain the purpose of this thread.
Cheers!
UPDATE - 11/14/2004
I've read several articles on Dij's alg, and I don't get it. Can anyone explain it in simpler terms to me? Here's how my self-solved pathfinding has been coming:
After the single path method above, I decided to do a sort of "branch out" method, where there is a list of paths, and it continuosly takes the path on the top of the list, expands it to all linked nodes, and puts all the new expanded paths back in the list at the end. In this way, if there is a path it will find it, and the first path which reaches the target will be the path that requires the shortest number of steps, but still not always the quickest path.
However, at one point I decided to make it so each path's first element( [0] ) is actually an index that is totalNumberOfNodes long and all visited nodes will have that element set to true. that way checking for loops is fast, as I just check the path's 'visited index' element0 to see if the requested linked node!=true. If it's not, it expands, and sets it to true(so it will never go back). So this made me think, what if I also made it so that the path stored the current total cost of travel(distance) in the path(at the second element -> [1]), and in this way when the branched out paths are put back in the list, rather than put in the end put it in order of shortest to largest. So in other words it's branching out to all paths, but it always expands the shortest path so far. Therefor, the first path to reach the target node MUST be the shortest possible path. It appears to work! Haven't done much testing yet. My current 15~20 node tests have returned calculations times of <10 milsec.
Updated ZIP with all 3 versions(Forward-Driven Single Path, Branch Out First Path, Shortest Branch).
rabbitkiller, did you ever take a look? What do you people think of this method? (The Shortest Branch method)?
(MX .fla, traces show most of the work, personal documentation included)
Last edited by >flashl!ght<; 11-14-2004 at 09:02 PM.
>flashl!ght<
All the normal names were taken.
Ron Paul was right.
Now what I came up with. Here's my original psuedo code idea:
precalculate:
nodesTotal
nodeWeights[nodesTotal][nodesTotal] - a 2D array grid containing values for every weight between every node
nodeLinkage[nodesTotal] - a 2D array, where every node has a corresponding array which contains all the IDs of linked nodes
init
path = []
discardPath = []
findPath(start,goal)
while(path[lastElement] != goal)
loop through all nodes linked to path[lastElement]
find linked node that is closest to goal node
that is not already in the 'path' array
and that is not in the 'discardPath' array
if node found
add to path
else if no node found
add path[lastElement] to discardPath array
remove path[lastElement] from path
if path is empty(all paths lead to a dead end) then there is no possible path
[edit]ug, for some reason the [ as ] tag isnt preserving my formatting(tabs)? maybe cause it came from wordpad[/edit]
-In the test I made, the little arrow guy was never made to actually do anything with the path, it's just calculated if it needs to.
-The nodes are all automatically connected to nodes that it has LOS to(bad idea for game, quick and easy for testing)
-clicking on a node shows all linked nodes(and traces all data associated with that node). you can see how messy the automated node linking is
-in short, it always attempts to get closer to the goal node, backing up whenever it hits a dead end(cant get to the goal). as soon as a path is found, its done(doesnt check for mutliple paths and compares which is best.)
The obvious innacuracy is that if there is an instance where one path starts out direct, then backtracks alot, and another path backtracks a little at first then gets very direct(and thus is quicker), the first will be found first(since it started out more direct) and thus will get used.
So the purpose is more to quickly find a path, if there is one, and attempt find one that at least isn't chosen totally randomly.
Again, the purpose is for people to take a look at the source, make their own changes, and see if we can come up with something cool. Otherwise I will have to just use someone else's idea(Dijkstra) - not that any of us could come up with something better of course
Last edited by >flashl!ght<; 11-06-2004 at 12:44 AM.
>flashl!ght<
All the normal names were taken.
Ron Paul was right.
You know... pathfinding is one of the most difficult tasks in programming (or maybe just "the most").
Originally posted by >flashl!ght< Before you laugh, this method is totally home-made. To me game-making *is* the game, so I didn't even bother searching google for pathfinding, I just tried to figure it out.
Well it was fun, but dumb.
I'm with you on that... I prefer to solve my broblems by myself (it might be dumb...), but the only thing that matters is experience.
I had enought of :
"Mathematical Analisis"
"Mathematical Logic and Applied Algorithms"
"Fuzzy Set Theory and Relation Algebra"
"Discrete Mathematics" (alot for pathfinding algs that I forgot)
"Programming Languages of High Level"
"Methods of Programming"
enoght already... or someone will think I'm showing off...
(I had not enought of english, probably....)
Now I would like some experience. I have to develop something myself. Pathfinding task will be different, depending on circumstances, therfore: basics are the same, but engine will be different depending on the game... You can't come up with something universal "fits all" technique. Even if you think you considered all parameters, there might be a new one...
Originally posted by >flashl!ght< Again, the purpose is for people to take a look at the source, make their own changes, and see if we can come up with something cool. Otherwise I will have to just use someone else's idea(Dijkstra) - not that any of us could come up with something better of course
I'll go thru that when I'll get some spare time (I know I should, but spare time like spare money it really does not exist in this world...)
Pathfinding is a serious stuff...
See you then, cheers!
Originally posted by rabbitkiller You know... pathfinding is one of the most difficult tasks in programming (or maybe just "the most").
No way! I did my first Path-Finding when I were 14 years old (with Amiga 500, ten years ago) and with no help at all (no internet, no articles, just thinking how it would work).
This I did in couple of days. The building is drawed from real prints.
The building isn't drawed whole by me, because this was a school-project (not finished yet).
Re: Re: Re: [Open Source] Node based pathfinding...
Sorry it's getting offtopic...
Originally posted by TeroLebe No way! I did my first Path-Finding when I were 14 years old (with Amiga 500, ten years ago) and with no help at all (no internet, no articles, just thinking how it would work).
That's cool...
But if it's a simple task of finding a way from one corner to another in a labyrinth with nothing but walls it's one thing. If you need for the AI of the opponents in your game...(ever played Warcraft 2? ever seen orcs stuck in the corner when they don't know what to do? think warcraf was designed by non-professionals?). Another thing is different types of terrain: if you got mud/swamp (charecter moves slow) plains (normal moovement) and roads (faster moovement). There's much more to pathfinding than you think...
One of the fundamental goals of an AI system is to avoid making the unit appear "dumb." At the root of this challenge lies one of the hardest problems to overcome efficiently and believably: pathfinding.
Re: Re: Re: Re: [Open Source] Node based pathfinding...
Originally posted by rabbitkiller Sorry it's getting offtopic...
That's cool...
But if it's a simple task of finding a way from one corner to another in a labyrinth with nothing but walls it's one thing. If you need for the AI of the opponents in your game...(ever played Warcraft 2?
I thought this tread was aboy only Path Finding. Ai, ok is much more difficult, and I've never said that my post was about that.
And never even thought of RTS-AI, couse it would be so difficult to do. I would use shortcuts, every unit would have own pre ordered "AI" (long-range units would stay on the back and melee on the front).
What else do you need pathfinding algorithms for?(considering you are a game developer...) Pathfinding is a very important part of AI. All that computer opponent have to do is to get from point "A"(current location) to point "B"(target's location) and attack the target(basically).
As I said it's not a rocket science if the task is simple, but things might get complicated, depending on the game.
hey, i strated some times ago a gameproject which also had to use waypoints .. well but after i'am created the waypoint editor i dont get time to build the game .. i also used the dijkstara algo.
nice tuts tony, your site is legendary! unfortunetly im not working with tiles right now. call me silly, but i just dont have fun trying to work with tiles, and to me the fun of game making is all that matters(this is why i dont sell or even release my stuff )
X-tender
checked out that waypoint pathfinding. it is very awesome! i hope to make one just like it. to clarify:
i did not use the dijkstara algo, because when i made this(its somewhat old) i hadnt done my homework and didnt even know about it. i just made it up on my own, which was fun but its not perfect, like dijkstara's :/ all mine does is basically continue to go to the next connected node that is closest to the target node, and if it hits a dead end it backs up. in this way it will always find a path, often a good path, sometimes the fastest, and sometimes a slightly roundabout way. but in the end a 20 node system calculates in 3-9 milsec(which only matter for realtime pathfinding, which is only needed if you have very variable info, ex moving nodes, changing noe weights/links)
at any rate, i've read 3 different articles on dijkstara's clever algo, and while i think i understand the gist, i cant imagine how to actually make it in Flash. and honestly i dont really understand except somehow in the back of my mind it makes sense.
>flashl!ght<
All the normal names were taken.
Ron Paul was right.
Originally posted by X-Tender ithink about to release the code maybe .. ;/ ..
woah! that would be very nice of you! i am dying for a real implentation of dijkstara 's algo, because like i said i dont totally understand it. maybe i need to jsut find a better article, one that doesnt assumed i know the basics of pathfinding terminology. i even found a video presentation, and the guy giving it even kept messing up and explaining things wrong, then backing up and saying "wait, its like this, wait let me think about this" i was so confused after 2 minutes i had to stop it: it could only be detrimental
at any rate, X-Tender, put me at the top of that list if you ever release even part of your code! You got my pathfinding algo
>flashl!ght<
All the normal names were taken.
Ron Paul was right.
I updated the original post, but here's a summary of how my pathfinding has evolved
v1
The path is built by finding the next linked node that is closest to the target node. If a dead end is reached, it backs up one step. In this way if there is a path, it will find one, but the accuracy of 'best-path' finding is not great. It usually finds a decent path(as long as the level is not oo maze like).
v2
Totally different, this uses a Branching out method, where it uses a list of paths, and it extracts the top path from the list, expands to all acceptable linked nodes(no loops), then puts all exanded paths at the end of the list. In this way, the first path that reaches the target is the path that requires the shortest number of steps(but not always the quickest path, so it's still not 100 percent accurate).
v3
Uses the branch out method, but rather than put the expanded paths in the end, it puts them back in in order of shortest in path distance(front/top of list) to longest in distance(end/bottom of list). In this way, the first path to reach the target must be the shortest path(I think ).
All 3 versions source included in the ZIP, and also my personal documentation(because I forget my ideas rather quickly ;-)
Must view in Flash, as most of the data is displayed via Trace actions. Take a look at the actual AS and tell me if you have any cool ideas and whatnot
Been fun, now I really need to figure out that Dijkstra's thing...
>flashl!ght<
All the normal names were taken.
Ron Paul was right.
). I've done alot with AI, including node based networks, squad based tactics, ect.
Reply With Quote
.. i also used the dijkstara algo.
