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

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.

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

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

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.

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.