• 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
uzipaz

Need advice on pathfinding implementation

6 posts in this topic

I have to write a simple 3D game in which I would like to implement an agent that can navigate through a map that has walls and simple static obstacles...

 

Now, I have studied the A* algorithm and was able to successfully write my own algorithm in c++... The algorithm runs on a rectangular grid with all the grids of being the same size... and can calculate optimal paths using euclidean distance as the heuristic...

 

Well, I have searched the internet and some game programming books and saw that just writing an A* algorithm is not enough, I need to have search space representation which in my case is a rectangular grid, translation of agents and 3D world knowledge between the algorithm and the game...

 

I was looking into some search space representation techniques and one of the most popular being navmesh and waypoints... I have read that pathfinding using waypoints in not recommended anymore and navmesh is the most popular among current AI developers...

 

Now, my issue is that I have never worked or programmed nav meshes before and this is the first time I am writing a game that has an AI component or NPCs...

 

How should I approach this? should I start by how to automatically generate navigation meshes for a level? or adjusting my algorithm to support navigation meshes?

 

I would gladly appreciate any advice...

0

Share this post


Link to post
Share on other sites

I'm not quite sure what your question is?  If it's trying to get pathfinding to work in 3D games, your rectangular grid should be workable, as most pathing cases (even in 3D games) tend to have a topology that maps down easily to 2D space.

 

What are you trying to consider as a part of your A* search and what is necessary for your game?  You don't always need to have full 3D world knowledge represented in your search space.  Most of the time, the 3D information involved is just portions of the walkable geometry so the game can map from the playable 3D space down to a representative graph for the pathing problem that is being solved, which often ignores most of the other 3D aspects of the game.

1

Share this post


Link to post
Share on other sites

I am rather a confusing individual... My point was that I would like to do this from scratch (as I did basic A*) so I could learn and understand the algorithm and the techniques... and I searched for Navigation meshes on the internet and several game programming books (including game programming gems, AI game wisdom). They don't give me any guidance about where to get started for this for newbies like me... but they describe a lot of different techniques and algorithms...

 

What you have described in your post is that I should stick with the rectangular grid... and it automatically does answers a lot of questions for me if I stick with a rectangular grid with each being of fixed equal size...

0

Share this post


Link to post
Share on other sites

Sticking to a rectangular grid/mesh can be easy from the initial implementation point of view, but they aren't without their own problems.  You have to consider the needs of your game to reach a good solution.  If your game's actual play space is grid based then the rectangular grid solution should work quite well, but if you have a full 3D continuous game space, you'll probably find lots of potential problems with using a grid (How do you generate the grid?  What resolution?  How many nodes are necessary to get good coverage/accuracy?).

 

Going with a triangulated mesh isn't a clear win either.  Given a 3D game, you could use some of the level geometry as a starting point for your triangulation, but you have to solve a lot of different problems (many of which don't have clear right answers/solutions) to get something that would be usable for your game.  If you have the expertise and the capability, you can have the mesh and it will give you a lot of nice properties, but getting the mesh in the first place is often very difficult.

 

Check out Recast/Detour https://github.com/memononen/recastnavigation. It's a very nice (so I've heard, never used it myself, but the features look impressive) navigation mesh generation library and if I'm not mistaken, it was used in Killzone: Shadow Fall!  The source is available so you can take a look at some of the techniques used.

 

If you're learning the basics of A*, pathfinding, and path following, I would highly recommend sticking to the rectangular grid as a starting point.  If you do in fact have a 3D game, it probably won't be ideal but it's simple enough that it should get you going and have you focused on getting a complete workable solution for AI agents to reason about your world and path through it.  Once you complete this, you could move on to having some sort of triangulated mesh.  If so, I would recommend reading up on Delaunay triangulations and more specifically, constrained Delaunay triangulations.

1

Share this post


Link to post
Share on other sites

As the other people have already said, depending on your needs, just use the retangular grids.
 

If you are set into using nav meshes or is doing that for study purposes I definitely would recomend you to take a look at this site:

http://www.critterai.org/book/export/html/2

 

It is a very detailed explaination on how recast works, definitely worth the time.

0

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