A Flash Developer Resource Site

Page 1 of 2 12 LastLast
Results 1 to 20 of 35

Thread: Pathfinding in NON tiled games

  1. #1
    Junior Member
    Join Date
    Jul 2010
    Posts
    11

    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?

  2. #2
    Custom User Title Incrue's Avatar
    Join Date
    Feb 2004
    Posts
    973
    Forget that and use tiles

  3. #3
    Junior Member
    Join Date
    Jul 2010
    Posts
    11
    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]

  4. #4
    Junior Member
    Join Date
    Jul 2010
    Posts
    11
    why i should? tiles are stupid and old. It's time for a new concept.

  5. #5
    Custom User Title Incrue's Avatar
    Join Date
    Feb 2004
    Posts
    973
    Because most of the solutions are made for tiles

  6. #6
    Pumpkin Carving 2008 ImprisonedPride's Avatar
    Join Date
    Apr 2006
    Location
    Grand Rapids MI
    Posts
    2,378
    Quote Originally Posted by artfabrique View Post
    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

  7. #7
    Junior Member
    Join Date
    Jul 2010
    Posts
    11

  8. #8
    Senior Member bluemagica's Avatar
    Join Date
    Jun 2008
    Posts
    766
    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:

  9. #9
    Junior Member
    Join Date
    Jul 2010
    Posts
    11
    Quote Originally Posted by ImprisonedPride View Post
    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...

  10. #10
    Custom User Title Incrue's Avatar
    Join Date
    Feb 2004
    Posts
    973

  11. #11
    Junior Member
    Join Date
    Jul 2010
    Posts
    11
    Quote Originally Posted by Incrue View Post
    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.

  12. #12
    Custom User Title Incrue's Avatar
    Join Date
    Feb 2004
    Posts
    973
    Put 4 nodes around each vector

  13. #13
    Custom User Title Incrue's Avatar
    Join Date
    Feb 2004
    Posts
    973
    Unless off course, if one vector crosses another, so its better that you have a level editor for that

  14. #14
    Junior Member
    Join Date
    Jul 2010
    Posts
    11

  15. #15
    Please, Call Me Bob trogdor458's Avatar
    Join Date
    Aug 2006
    Location
    Pensacola, FL
    Posts
    915
    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

  16. #16
    Junior Member
    Join Date
    Jul 2010
    Posts
    11
    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

  17. #17
    Pumpkin Carving 2008 ImprisonedPride's Avatar
    Join Date
    Apr 2006
    Location
    Grand Rapids MI
    Posts
    2,378
    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

  18. #18
    Pumpkin Carving 2008 ImprisonedPride's Avatar
    Join Date
    Apr 2006
    Location
    Grand Rapids MI
    Posts
    2,378
    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

  19. #19
    Please, Call Me Bob trogdor458's Avatar
    Join Date
    Aug 2006
    Location
    Pensacola, FL
    Posts
    915
    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

  20. #20
    Junior Member
    Join Date
    Jul 2010
    Posts
    11
    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
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center