Printable View
Hi all.
I've completely stuck in pathfinding problem.
Imagine tha we have a "map" as a array of vectors (mathematical)
each shape segment (wall) has start point and end point(so delta is our vector)
how do i perform pathfinding in non tile-based map?
Forget that and use tiles
Here is scheme.
Lines - vectors.
small dots - points.
A & B - start and destination
[IMG]http://lh4.ggpht.com/_p3pc0kJP9Dw/TEM98bk7bcI/AAAAAAAAAS8/gxJYgoK
iOJ4/Untitled-1.jpg[/IMG]
why i should? tiles are stupid and old. It's time for a new concept.
Because most of the solutions are made for tiles
Tile-based approaches came second, mate.Quote:
Originally Posted by artfabrique
To answer your question, a simple tree of vector nodes should solve your problems quite readily. Have a go at google. It's where I found your answer. :)
http://lh4.ggpht.com/_p3pc0kJP9Dw/TE...Untitled-1.jpg here is the situation ;)
ok. i know how to find the shortest way jumping by v.nodes. BUT where i should get this nodes? in the beginning i have only "wall corner" nodes...Quote:
Originally Posted by ImprisonedPride
http://lab.polygonal.de/2007/06/13/d...e-graph-class/
But you still should use tiles
As you see on "Figure 3" there - the nodes already defined. The question is how to calculate where to set a node. How will algorythm know that this node should be here.Quote:
Originally Posted by Incrue
Put 4 nodes around each vector
Unless off course, if one vector crosses another, so its better that you have a level editor for that
how?Quote:
Originally Posted by Incrue
http://lh6.ggpht.com/_p3pc0kJP9Dw/TE...Untitled-2.jpg
http://lh6.ggpht.com/_p3pc0kJP9Dw/TE...Untitled-3.jpg
I'm thinking you only need those corner nodes, as well as an extra one being your destination
I've never looked for proof, it's just that aiming for corners is how I've determined the shortest path in every game I've played since forever
You set up a loop to check out what series of nodes will get you there the quickest (or at all), making sure it knows which nodes are accessible by certain nodes and which aren't, and you're done
I could whip up an example if you like
YESS! i've found one very good article BUT stil no answer how to build graph
here is an artice - scroll to the end - that's what i'm talking about.
http://hq.alert.sk/~mandos/fmfi-uk/I...y/smartmov.pdf
here is illustration for this article:
http://algolist.manual.ru/games/gif/path_fig11.png
Pretty sure you could cast a vector from the player to the endpoint and test for the closest vector intersection, then cast vectors from each endpoint of that vector to the endpoint and retest until you have a list of shortest move vectors.
Let me draw a horrible mspaint graphic depicting this...
http://img844.imageshack.us/img844/6325/54494424.png
Ok so start at "start" and we're headed to "end". Place a vector going directly from start to end and check for the closest vector intersection. In this case it is vector AB. Now, using the endpoints of AB, we draw two more vectors to end again and check these two vectors. Immediately, B is not usable since it goes through (itself) another block (it might be possible to use the vector below AB, but I'm not sure how to obtain it at this point). So we use A. Get the closest vector intersection from A to End which is vector CD. Use the end points of CD and shoot two vectors to end. C is unusable just like B was so we use D. Get closest intersection from D to end which is EF. Use end points of EF and shoot two vectors to end. E is unusable like D and B so let's try F. Success! F to End is clear.
Final path: Start, A , D, F, End.
No idea if this is feasible at all. Just the first idea that popped into my head.
That works, but almost every method excluding brute force methods has a scenario where it doesn't work, or the character looks very silly finding its path
One scenario for such a method would have the hero running into a tunnel, only to run back out realizing it's a dead-end
Truth is, I don't think there's an all-powerful algorithm out there that can solve every situation efficiently
Best bet is to set up your own custom node tree such-and-such based on your level's design
Have a giant maze thing randomly in your level?
Don't waste resources trying to solve it during run-time, just hard-code the solution in there
but what if first figure will be this:
http://lh6.ggpht.com/_p3pc0kJP9Dw/TE...Untitled-4.jpg
and actually they will not be squares
this is for Online Quest/Adventure Game Editor. i want to make a veeeeeeery easy to use editor so illustrators and designers could just upload graphics, do several clicks and get a game and share it.Quote:
Originally Posted by trogdor458
The shapes those vectors make up is irrelevant. What's important in my suggested theory is that you always scan the closest intersection.Quote:
Originally Posted by artfabrique
Well, hrmmQuote:
Originally Posted by artfabrique
I guess what I would do is when you finish making a level, have it figure out its own efficient set of nodes that can be used later when actually playing the game
Players won't mind waiting a few seconds for processing after they make a level compared to how much they would mind waiting a few seconds every time they want to pathfind somewhere
So basically: player puts in a random maze, computer solves random maze, computer stores solution to maze in the level code so it doesn't have to again later
Lots of programs do this sort of thing, not just for pathfinding
its called a navigation mesh and like trogdor pointed out the best way is too manually place nodes and connect them up. Its tedious but gives you the best results.
Alternatively you could subdivide the map like a grid and connect up grid nodes to other nodes which do not overlay graphics (using some bitmapData getPixel methods or similar). Then optimize it further by joining empty regions of nodes together, so you end up with a quad tree like structure.
Yeah nodes is the best bet if your not using tiles.
But he said he'll be unable to make the mesh himself, as he'll need pathfinding for custom-made user-levels, and doesn't want to put them through the tedious process themselves
I can't say I've ever tried it and I don't feel like doing research either, but I have a few ideas on how to automate the process
I could give it a shot =\
The best approach I have found is to subdivide the area then merge open spaces. Once done the nodes can be created at the grid square edges and link between grid nodes. Its not totally 100% accurate but will give you nice distances from wall edges and is fast to compute.
Another approach is to extrude the end points of walls and create several corners for 1 edge. However, problems can occur when the extrusion falls inside other geometry (corridors and close walls). Figuring out how much to extrude by becomes very costly on the CPU if lots of other geometry exists, you basically have to loop over all geometry and determine distances between walls.
Then comes the problem of linking up nodes to other nodes from other sets of geometry that may be hundreds of pixels away. You must raycast from every edge to every other edge in order to determine the visibility mesh (very expensive), nodes * nodes * walls. You also need to disregard nodes that fall within the extrusion zone, also very bad.
Another way is to triangulate the area using an algorithm called CDT "CONSTRAINED DELAUNAY TRIANGULATION" http://www.geom.uiuc.edu/~samuelp/del_project.html which creates the skeleton mesh. You then loop over traingles and extrude inwards at triangle points linking adjacent triangles together. You could also go with a hybrid here and create nodes at the triangles center rather than edges.
He could just write something that places nodes 20 or 30 pixels apart like a tile system and removes nodes that are on top of objects. Then use a line of site sort of thing in the movement code to determine whether 2 points cross an object if not move to the next.
When I give it a shot I'm going to split the field into convex polygons linking from all their open sides
Sounds similar to what malee suggested closer to the bottom of his post
And yes, was going to make nodes in the middle of each one
perfectly selfexplanatory picture, thanks for posting!Quote:
Originally Posted by artfabrique
edit: seems like others commenting here do not see a solution in this picture? I thought arrows would give it out :)
edit2: afterthought is telling me that there are multiple solutions, in fact, whole tree, if you turn arrows around every time there's an intersection... sounds like nice experiment to do some day.
I have a question on this subject. This guy is just doing A to B, which seems to be static for each level (being that on any given level it wont change until you are on the very next level). Now what if you have a movieclip (Enemy) who needs to path find to another movieclip (A character you move)? The path will always be changing as you move and there is no already solved answers that you could do..
(Sorry for the side question)
It requires a bit of cheating on part of the AI. Baddie will have to anticipate where the hero will be and use that as a static reference point for path finding.
Lets say the baddie wonders around untill you are in its sight area.
When it sees you it chooses a path to that location, then then it moves a step toward you, it updates its path again (because you most likley moved), would this be a bad idea with 30 movie clips? or 30 baddies.. :\
This might be relevant to the original discussion, but for a user-generated map, couldn't you apply a basic mesh and use some sort of flocking routine to force the nodes outside of any vectors?
You could only have the nearest baddie do the pathfinding routine, and then all nearby baddies follow him.
And even if you're moving, you wouldn't need to find the path again. You only need to find the path again once the player has moved to another node on the pathfinding mesh, and then the pathfinding can be divided over the next few frames.
Actually, to find the new path after the player has moved, you could start the pathfinding routine from the node that was picked last. Not only would this be much much faster, but it's almost more natural, that the AI is following the player.
Another optimization could be to leave traces on each node, and if a node has already been touched, then you just copy the rest of the path from that node that was already calculated, given that all your baddies are traveling towards the same target.
P.