A Flash Developer Resource Site

Page 2 of 2 FirstFirst 12
Results 21 to 35 of 35

Thread: Pathfinding in NON tiled games

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

  2. #22
    Pumpkin Carving 2008 ImprisonedPride's Avatar
    Join Date
    Apr 2006
    Location
    Grand Rapids MI
    Posts
    2,378
    Quote Originally Posted by artfabrique View Post
    but what if first figure will be this:
    http://lh6.ggpht.com/_p3pc0kJP9Dw/TE...Untitled-4.jpg

    and actually they will not be squares
    The shapes those vectors make up is irrelevant. What's important in my suggested theory is that you always scan the closest intersection.
    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

  3. #23
    Please, Call Me Bob trogdor458's Avatar
    Join Date
    Aug 2006
    Location
    Pensacola, FL
    Posts
    915
    Quote Originally Posted by artfabrique View Post
    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.
    Well, hrmm
    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

  4. #24
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    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.
    lather yourself up with soap - soap arcade

  5. #25
    formerly hooligan2001 :) .hooligan's Avatar
    Join Date
    Mar 2008
    Posts
    405
    Yeah nodes is the best bet if your not using tiles.
    World Arcade | Facebook | Twitter - Follow MEEEE! or not......

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

  7. #27
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    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.
    lather yourself up with soap - soap arcade

  8. #28
    formerly hooligan2001 :) .hooligan's Avatar
    Join Date
    Mar 2008
    Posts
    405
    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.
    World Arcade | Facebook | Twitter - Follow MEEEE! or not......

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

  10. #30
    Senior Member realMakc's Avatar
    Join Date
    Oct 2002
    Posts
    927
    Quote Originally Posted by artfabrique View Post
    perfectly selfexplanatory picture, thanks for posting!

    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.
    Last edited by realMakc; 07-20-2010 at 01:58 PM.
    who is this? a word of friendly advice: FFS stop using AS2

  11. #31
    Senior Member
    Join Date
    Apr 2009
    Posts
    138
    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)

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

  13. #33
    Senior Member
    Join Date
    Apr 2009
    Posts
    138

    example

    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.. :\

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

  15. #35
    Senior Member Pazil's Avatar
    Join Date
    Sep 2006
    Location
    Ontario, Canada
    Posts
    913
    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.
    WIP-ZOMBIES

    I love vegetarians! More meat for the rest of us!

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