Jump to content

  • Log In with Google      Sign In   
  • Create Account

Working with A* in a 3D voxel world


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 29 January 2014 - 06:56 PM

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



Sponsor:

#2 ferrous   Members   -  Reputation: 2022

Like
1Likes
Like

Posted 29 January 2014 - 08:39 PM

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.



#3 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 29 January 2014 - 10:45 PM


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



#4 ApochPiQ   Moderators   -  Reputation: 15824

Like
0Likes
Like

Posted 29 January 2014 - 10:53 PM

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.

#5 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 29 January 2014 - 11:51 PM

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



#6 ApochPiQ   Moderators   -  Reputation: 15824

Like
0Likes
Like

Posted 30 January 2014 - 12:41 AM

Hmm... if your voxel set is changing frequently, navmeshes probably wouldn't be a win.

#7 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 30 January 2014 - 12:50 AM

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.



#8 KnolanCross   Members   -  Reputation: 1317

Like
0Likes
Like

Posted 30 January 2014 - 06:05 AM

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.


Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#9 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 30 January 2014 - 09:13 AM

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.



#10 KnolanCross   Members   -  Reputation: 1317

Like
0Likes
Like

Posted 30 January 2014 - 09:39 AM

Well, if you are interested in navmesh generation, take a look here:

http://critterai.org/projects/nmgen_study/


Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#11 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 30 January 2014 - 09:58 AM

Well, if you are interested in navmesh generation, take a look here:

http://critterai.org/projects/nmgen_study/

I've seen his site before...and that's where I found JPS. Is this something that's good for dynamic environments that can change frequently?



#12 KnolanCross   Members   -  Reputation: 1317

Like
0Likes
Like

Posted 30 January 2014 - 01:24 PM

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, 30 January 2014 - 01:43 PM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#13 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 30 January 2014 - 01:45 PM

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, 30 January 2014 - 01:46 PM.


#14 ferrous   Members   -  Reputation: 2022

Like
0Likes
Like

Posted 11 February 2014 - 04:25 PM

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.



#15 studentTeacher   Members   -  Reputation: 852

Like
0Likes
Like

Posted 12 February 2014 - 01:10 AM


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.



#16 KnolanCross   Members   -  Reputation: 1317

Like
2Likes
Like

Posted 12 February 2014 - 09:40 AM

@studentTeacher

It is dangerous to go alone. Take this:

 

https://github.com/Yonaba/Jumper/blob/master/jumper/search/jps.lua


Edited by KnolanCross, 12 February 2014 - 09:40 AM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS