-
Pathfinding in NON tiled games
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?
-
Custom User Title
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.
-
Custom User Title
Because most of the solutions are made for tiles
-
Pumpkin Carving 2008
Originally Posted by artfabrique
why i should? tiles are stupid and old. It's time for a new concept.
Tile-based approaches came second, mate.
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.
The 'Boose':
ASUS Sabertooth P67 TUF
Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
8GB G.Skill Ripjaws 1600 DDR3
ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
New addition: OCZ Vertex 240GB SATA III SSD
WEI Score: 7.6
-
-
Senior Member
If you like me, add me to your friends list .
PS: looking for spriters and graphics artists for a RPG and an Arcade fighting project. If you can help out, please pm me!
My Arcade My Blog
Add me on twitter:
-
Originally Posted by ImprisonedPride
Tile-based approaches came second, mate.
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.
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...
-
Custom User Title
-
Originally Posted by Incrue
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.
-
Custom User Title
Put 4 nodes around each vector
-
Custom User Title
Unless off course, if one vector crosses another, so its better that you have a level editor for that
-
-
Please, Call Me Bob
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
-
Pumpkin Carving 2008
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.
The 'Boose':
ASUS Sabertooth P67 TUF
Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
8GB G.Skill Ripjaws 1600 DDR3
ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
New addition: OCZ Vertex 240GB SATA III SSD
WEI Score: 7.6
-
Pumpkin Carving 2008
Let me draw a horrible mspaint graphic depicting this...
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.
The 'Boose':
ASUS Sabertooth P67 TUF
Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
8GB G.Skill Ripjaws 1600 DDR3
ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
New addition: OCZ Vertex 240GB SATA III SSD
WEI Score: 7.6
-
Please, Call Me Bob
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
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
|