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

Working with A* in a 3D voxel world

15 posts in this topic

In my voxel game, I'm looking at making NPC's use A* to path-find. I've got a couple parts of this I'm having trouble figuring out/implementing. Mainly, I'm having difficulty when it gets to two different (but possibly occurring together) scenario's:

  1. There are a ton of NPC's trying to path-find, and
  2. There's a large distance to path-find to.

I'm not sure how to choose between multi-threading, using multiple frames, or exactly how to implement this. Any suggestions, paper's, books, websites, etc?

 

Thanks,

ST

0

Share this post


Link to post
Share on other sites

In my voxel game, I'm looking at making NPC's use A* to path-find. I've got a couple parts of this I'm having trouble figuring out/implementing. Mainly, I'm having difficulty when it gets to two different (but possibly occurring together) scenario's:

  1. There are a ton of NPC's trying to path-find, and
  2. There's a large distance to path-find to.

I'm not sure how to choose between multi-threading, using multiple frames, or exactly how to implement this. Any suggestions, paper's, books, websites, etc?

 

Thanks,

ST

 

If you have multiple NPCs, you will want multi threading, or some other form of start stopping.  What language are you using?  

 

for the second, you can split things into regions, or just have the model start moving in advance, taking the best known path so far after x cycles, and then just readjust when you find the true path.  You will not get the most optimal path that way, but it will get the unit moving if the pathfinder is taking too long.

1

Share this post


Link to post
Share on other sites


If you have multiple NPCs, you will want multi threading, or some other form of start stopping.  What language are you using?

 

I'm using Java, because I'm most familiar with it. I will have up to a couple hundred NPC's at most, but at that point they'll be moving as units (like an army) so they can compute their movements together. Mainly there might be 6 or 7 separate groups of moving NPC's at far distances at a time.

 


for the second, you can split things into regions, or just have the model start moving in advance, taking the best known path so far after x cycles, and then just readjust when you find the true path.  You will not get the most optimal path that way, but it will get the unit moving if the pathfinder is taking too long.

 

Regions is probably the way I'm going to do this, for the reasons you stated. Thanks for that idea :)

 

So if I understand what you're saying, I can create some type of multithreading setup for each NPC, or I could create another form of start-stopping (swapping maybe?). I also take my world (broken up in Regions, made up of what I create my world with (zones, which are stacks of chunks)) and path-find within a region, and only path-find in the region the NPC is in...?

 

Another quick question: When do you cut off an NPC? Should I have it allow the NPC more processing time if there's only 1, but share the time when there's 200 NPC's or allocate the same amount of time whether it is 6 or 200 NPC's....

 

I'll have to do my reading again on multithreading.....I've learned a lot about it, especially in some of my courses, but haven't done a full-blown application yet.....

0

Share this post


Link to post
Share on other sites
I wouldn't mess with multithreading for this.

A good A* implementation can handle the demands you're describing easily, provided you do some simple things, like rate-limit path searches. So for example you can allow one hundred "short" searches or twenty "long" searches in one game tick, say; any search beyond quota gets put in a waiting list for the next frame. You can also attach priorities to this if you really want but generally it isn't necessary. Even running at 25Hz you get 25 batches of path searches per second, which should be ample for a few hundred NPCs.

Other useful tricks are hierarchical A* (which has been mentioned); navmeshes, which can be constructed from voxelized data pretty easily; and dynamic resolution, where some parts of the world get more A* nodes per unit volume than others.
0

Share this post


Link to post
Share on other sites

I wouldn't mess with multithreading for this.

A good A* implementation can handle the demands you're describing easily, provided you do some simple things, like rate-limit path searches. So for example you can allow one hundred "short" searches or twenty "long" searches in one game tick, say; any search beyond quota gets put in a waiting list for the next frame. You can also attach priorities to this if you really want but generally it isn't necessary. Even running at 25Hz you get 25 batches of path searches per second, which should be ample for a few hundred NPCs.

Other useful tricks are hierarchical A* (which has been mentioned); navmeshes, which can be constructed from voxelized data pretty easily; and dynamic resolution, where some parts of the world get more A* nodes per unit volume than others.

 

How is generating a navmesh in real-time, with a dynamic environment? I've heard about them but haven't looked too deep into them yet. Would a navmesh be created on every chunk update, just like the mesh is? My voxelized terrain is much like a Minecraft setup with blocks, rather than having LOD or anything like that...

0

Share this post


Link to post
Share on other sites

Yea, the environment is dynamic, especially when in battle (which means a lot more NPC's in one place, too). Movement is easy enough to define (1-block jumps up is okay, and some calculated drops greater than 2 or 3 blocks is also allowed) but besides that....I don't have very much to go on.

0

Share this post


Link to post
Share on other sites

Did you code the A* yourself? What kind of graph you are using for it? If it is a grid, you can try to use JPS, it is a huge performance improve for big paths.

0

Share this post


Link to post
Share on other sites

Did you code the A* yourself? What kind of graph you are using for it? If it is a grid, you can try to use JPS, it is a huge performance improve for big paths.

 

The A* is written by me -- I can't really find an application of A* anywhere for 3D dynamic voxel terrain. The voxels make a grid themselves, with movement in 4 directions (I'll have to look into diagonal movement too...I want to use it but it sometimes means a lot of extra checking). The issue is that some of the NPC's will have to travel hundreds of blocks and need to path-find that far. I'll take a look at JPS, it looks interesting.

0

Share this post


Link to post
Share on other sites

JPS in a grid yes, grid implementations are the easier and fastest updatable struct you can use for changing envirnoment as all you need to do is mark the point as open or closed (and recalculate the path, but you would need to do that with pretty much any representation).

 

That being said, notice that grid implementations are likely be slower than navmeshs and consume much more memory.

 

I made a comparassion not long ago of a small A* study I made, you can see how much faster the JPS is: http://www.gamedev.net/topic/651968-binary-heap-vs-list-a-my-humble-performance-comparison-updated-with-jps/

Edited by KnolanCross
0

Share this post


Link to post
Share on other sites

Ok I'm going to say a little more on my implementation of my game so people know how things are running under the hood:

  • The game is voxel-based, like Vox or Minecraft.
  • The world is made of an 32x32 grid of Zones. Each Zone is made up of 1x16x1 Chunks, and each chunk is made of 16x16x16 voxels, arranged in a rolled out, 1-D array of shorts (Voxel ID's). The world is then 496x256x496 voxels. This might extend as far as 1024x1024x256 voxels if I want to push my graphics card and optimize/multithread my single-threaded game engine, pushing terrain data as far as a little over half a gigabyte of terrain data.
  • For path-finding, I query these voxel's faces to see what areas the NPC can move from. This way, no NavMesh or anything like that needs to be generated, saving on a ton of memory. Querying for 10-100 voxels a frame is no problem.

In THIS case, I'm looking at how this scales, and if I need to generate any type of navigational mesh. Obviously the path points I set for the NPC is every block; maybe I can save some memory with spreading out points (JPS may help with this) using an optimized navigation mesh? Terrain data takes up almost 256Mb data in memory, and re-meshing chunks takes a bit of time too. I need to balance time and memory for AI navigation.

 

What I've seen so far is that I can limit the number of queries an NPC makes based on two things: frame length and number of NPC's. Maybe only navigate 1 zone at a time (or possibly something a little larger, since NPC's are 1x1x2 voxels in size and a zone is 16x16 on it's top face so...maybe 2x2 or 4x4 zones at a time...?) to save processing power. How would this scale, though, to large castle, city walls, etc...? Would the NPC be forced then to follow the side of the wall all the way around...?

Maybe I'll have to play with this some more, and I'm just over-thinking this right now.

Edited by studentTeacher
0

Share this post


Link to post
Share on other sites

I don't think a navmesh is the way to go for terrain that constantly changes, and is already in a grid.

 

You could try to keep track of entrances/exits to Zones.  You can then split your pathing up into a local within a Zone traversal, and a macro zone-to-zone traversal.  Granted, I'm not sure how expensive it will be to keep track of entrances/exits to zones for your game, it could be more overhead than it's worth.

 

I think you have the right idea that it's best to start simple,and optimize only if you need it, as it may turn out your satisfied with the simple solution.

0

Share this post


Link to post
Share on other sites


I think you have the right idea that it's best to start simple,and optimize only if you need it, as it may turn out your satisfied with the simple solution.

 

I think you're right. I'm just going to use A* with JPS and calculate per-frame for NPC's. They'll also have a limit to their search so their path list doesn't get too long :P But 32-64 path-points per NPC should be good for now.

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