-
Need Fast pathfinder
Hello !
I am trying to make a simple "tower defense" game, where you put towers on a tile-based map to stop bad guys from going through.
I tried understanding pathfinding from what I found on the internet... and it is too much for me right now I think.
So I was wondering, do you people know where I could get a fast and simple pathfinder ?
Terrain has no different costs and map size is about 25x40 btw.
Thx alot.
P.S. I know this has probably been posted before, but I couldn't find anything... sorry...
-
here's the best link that i know of..think you can even download some source code and run it
http://jobemakar.blogspot.com/2008/0...thfinding.html
-
Developer
-
A* and Dijkstra are both slow and very accurate, to what I have read around the web...
But I am talking about 5-20 units serching path on a dynamic map with no terrain cost... so A* seems like a bad choice.
I just read about "tracing", "robust tracing" and such... anyone could give me information about those ?
-
Could just have one unit find the path at the start of the round, then the rest of the units use waypoints. then in the movement function, you could have each unit check if they encounter a wall between 2 waypoints in case the tower builder placed a tower after the path was found.
otherwise, just disable the builder from building while the units are moving.
-
look in the flashkit movie section or somewhere else where there is a simple and plain fla example.
I recently had to dig up this topic as well to write a pathfinding that is very fast (+60 units computing every few seconds) on quite complex terrain.
In the past I experimented alot with node based pathfinding which usually requires manually or half automated node placement- but on very large and detailed maps it did not worked out well for me.
This time I experimented with a dynamic grid that is placed over a image (greyscale) or movieClip and check within that grid wich cells are acessable
Usually in A* you try to find multiple ways and sort them at the end based on their effectness- but I found a way to do a quick and dirty pathfinding searching basicly only 1 path. It works for 80% of the cases I had- and in case it fails it walks at least as far as possible.
I might release a as3 class at some time but not this year
-
Originally Posted by Flyingcow
Could just have one unit find the path at the start of the round, then the rest of the units use waypoints. then in the movement function, you could have each unit check if they encounter a wall between 2 waypoints in case the tower builder placed a tower after the path was found.
That is the way I thought I'd do it, but I can't figure out how to make it work when the player adds towers...
And lets say he adds a whole lot of them, wouldn't that mess up the path completly if you don't search for a new one ? Or maybe I'm just not understanding how you'd do it...
If I can't find anything, I'll probably just make it impossible to build towers during waves.
-
Funkalicious
Just go through all the paths of the troops currentl on screen, and check if it goes through the cell that a new tower has been placed on. If so, recalculate the route. You might be able to shave something off, by only making a route which connects the two pieces of the original route and stuff it in between.
-
Senior Member
First off, A* and Dijkstra's algorithms are both the same, except that A* is an optimization of Dijkstra's by doing a priority first search. And A* will usually only find one way, just it starts searching several, but then only completes one...
The best way I would suggest is to do the algorithm (I'm not sure if there's even an exact name for it or not) that find a path as long as it's not convex, but then just have the baddy check if a)it's visited the same square before, and b) if it's going in the same direction as it had already before...
Render, that looks like a pretty neat thing you've got going there...but it seems as though your algorithm can't handle convex (u-turns) shapes? Just the example you posted doesn't have any areas like that, but the only one you really had in there was at the beginning, and it seems as though you valued x movement over y? Am I wrong? Just wondering, since if I am wrong, your algorithm is truly amazing!
P.
WIP-ZOMBIES
I love vegetarians! More meat for the rest of us!
-
Senior Member
Sorry...Double post...computer locked up for a second...
WIP-ZOMBIES
I love vegetarians! More meat for the rest of us!
-
Whenever you have a graph search problem, A* is generally the best solution. As well as always producing an optimal path, it is very efficient compared to other methods.
Tracing and robust tracing will either fail or produce very unnatural paths.
From what I can see in render's post it performs a naive search in the direction of the target and then smooths the path.
Since the start and end tile are always the same you can take some pretty serious liberties in your pathfinding as well. In all truthfulness, the chances are that you will only have to calculate the path once after each tower is built and reuse that path for each unit.
The greatest pleasure in life is doing what people say you cannot do.
- Walter Bagehot
The height of cleverness is to be able to conceal it.
- Francois de La Rochefoucauld
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|