• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
ngoaho91

Pathfinding avoid a list of polygon

14 posts in this topic

Hello, i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very slow. I'm looking for an advice from who experienced  biggrin.png

At very first, i have a list of obstacle as polygon like that

 

[attachment=20213:map.png]

 

i decided to build a pathfinding graph, then i travel all pairs of node, connect them if the connection segment doesn't intersect any polygon. this process have O(n^2) time complexity.

 

[attachment=20214:graph.png]

 

after that, on every path query, i try connect every node to A(startnode) and B(goal node), then do dijstra to find path. this process have O(2n) + O(nlogn) time complexity.

 

[attachment=20216:query graph.png]

 

[attachment=20217:path.png]

 

 

That's all, my algorithm works fine(even it's slow) if the environment is static, no insert, remove obstacle. But when the environment turn to dynamic, such as a obstacle removed, i need to rebuild pathfinding graph(O(n^2)), my fps extremely decreased, 120 to 10.

 

Is there a more professional aproach to solve my problem?

Edited by ngoaho91
2

Share this post


Link to post
Share on other sites

@cormet, actually the algorithm build & rebuild graph cause the slow. dijstra are works fine here but i will try a*.

@aardvajk, i was think of that way before, as i see from here, http://www.ai-blog.net/archives/000152.html the generated graph are poor. so when the agents growns, many paths should duplicate. then agents would collide many times. then evade process occurs frequencely and slow down the game.

@ferrous: please show me those algorithms :D

0

Share this post


Link to post
Share on other sites

@pink horror: i tested with 65 nodes, and do the test 100 times per frame, i'm too lazy to draw a map 6500 nodes biggrin.png. and yeah right, i forgot to mention intersect condition.

 

 


How do you collide a line segment against a polygon?

first i do simple step, collide the aabb of them. if overlap, i do complex step, check collide that line segment to every single line segment of the polygon.

 

 


How do you search for which polygons to test?

i'm using quad tree to divide polygon set. the time to find which polygons to test seem cost logN time(n=number of polygon)

Edited by ngoaho91
2

Share this post


Link to post
Share on other sites

Why don't you use the good old grid + A* pathfinding?

 

It is a pretty simple approach, limit the amount of paths calculated and you should have an OK FPS rate.

 

If you need better approachs you will have to look for a better graph representation for A* than a grid.

 

I suggest reading:

http://theory.stanford.edu/~amitp/GameProgramming/ (A LOT of information on A*)

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html (Map representation only)

Edited by KnolanCross
0

Share this post


Link to post
Share on other sites

Alright so you have three major steps to use navmeshes.

 

1.  navmesh generation

  You can do this manually if you want, or try to autogenerate it yourself, or get a thirdparty library (Recast/Detour)

  This looks like a decent article to start with: http://critterai.org/projects/nmgen_study/

 

2.  navmesh traversal (this is basically A* with some smoothing, a lot of the same algorithms apply)

  Check Knolan's links above, they do have a Navmesh entry

3.  Navmesh cutting

  Unfortunately I'm having trouble finding good links, I know there "Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision" by Paul Marden and Forrest Smith (AI Game Programming Wisdom 4), but that book is out of print, and uh, yeah, $599 for a used copy is insane.  (I have no idea why there isn't an e-book version out there for purchase)

There is this paper: http://users.ices.utexas.edu/~acook/papers/CAVW_Dynamic_ECM.pdf, and it's accompanying video http://www.youtube.com/watch?v=tH9dNESH4ic

Edited by ferrous
2

Share this post


Link to post
Share on other sites

Why don't you use the good old grid + A* pathfinding?

 

It is a pretty simple approach, limit the amount of paths calculated and you should have an OK FPS rate.

 

If you need better approachs you will have to look for a better graph representation for A* than a grid.

 

I suggest reading:

http://theory.stanford.edu/~amitp/GameProgramming/ (A LOT of information on A*)

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html (Map representation only)

 

i'm not that good to make grid movement smooth biggrin.png. i compare AOE to starcraft, i think both use grid map, but starcraft has micro skill, AOE not. smooth unit movement is important for micro.

 

 

 


Alright so you have three major steps to use navmeshes.

 

i searched and found people talking about navigation mesh, but i don't understand why there are so many nodes that doesn't belong to any obstacle. i think a shortest path never travel through them. why are they there?

Edited by ngoaho91
0

Share this post


Link to post
Share on other sites


i compare AOE to starcraft, i think both use grid map, but starcraft has micro skill, AOE not.

StarCraft 2 uses navigation meshes with A* and a funnel algorithm for pathfinding. Unless you're talking about StarCraft 1, which used a 2D grid and A*.

0

Share this post


Link to post
Share on other sites

yeah, starcraft 2 is my goal, i'm talking about it's terrain and moving system. i'm already have a set of 2D assets that can form the game. but building assets can't fit in grid. i mean it's shape isn't square or rectangle or diamond, so i think of 'polygon' solution above. but it's seem unofficial and no one do it. i feel a little awkward

Edited by ngoaho91
0

Share this post


Link to post
Share on other sites

As mentioned multiple times, use navigation meshes, they're your best bet.

Is there a more professional aproach to solve my problem?

The following are two libraries. Recast Navigation generates navigation meshes and Detour is a powerful pathfinder, capable of searching for paths as well as handling the movement of agents.

https://github.com/memononen/recastnavigation

 

With that you can

  1. Automatically re-generate navigation meshes on the fly.
  2. Search paths for different sized agents.
  3. Control movement of agents using advanced flocking algorithms.
2

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0