Time budget for pathfinding of 100 npcs at a time.
by Darian Hickman · in Technical Issues · 02/13/2007 (10:11 pm) · 8 replies
I've been producing a 2D RTS inside TGB for the past 4 months and one of the big time consumers is deciding how to implement pathfinding for all the villagers running around inside my village that I'm modelling. What's a reasonable amount of time to allocate for implementing pathfinding that can handle 100 npcs at a time?
This is the writeup I posted at http://www.villagethegame.com:
We need to create a lightweight pathfinding algorithm to support 100 villagers running around on one map that ranges in size from 64x64 tiles to 128x128 tiles. This pathfinding algorithm should be written in C, or C++. The map on which villagers are moving contains heavily trafficked routes as well as completely untrafficked areas such as river or forest. The AI should be able to handle basic collision between two villagers and reroute them efficiently. A typical map will have a town center which is a very common destination for the villagers and 20 to 80 huts which are another common destination but more spread out. The edges of the map do not wrap around like PAC-man. The map just ends there. The villagers can move in 8 directions only. up, down, left, right and the 4 diagonals in between.
This code will be incorporated into a realtime strategy game built on Torque Game Builder. We'll be testing at the minimum system specs that GarageGames recommends on Windows.
Windows Minimum: 500 MHz processor, 256 MB RAM, Windows 98, OpenGL or DirectX compatible accelerated 3D video card.
This is the writeup I posted at http://www.villagethegame.com:
We need to create a lightweight pathfinding algorithm to support 100 villagers running around on one map that ranges in size from 64x64 tiles to 128x128 tiles. This pathfinding algorithm should be written in C, or C++. The map on which villagers are moving contains heavily trafficked routes as well as completely untrafficked areas such as river or forest. The AI should be able to handle basic collision between two villagers and reroute them efficiently. A typical map will have a town center which is a very common destination for the villagers and 20 to 80 huts which are another common destination but more spread out. The edges of the map do not wrap around like PAC-man. The map just ends there. The villagers can move in 8 directions only. up, down, left, right and the 4 diagonals in between.
This code will be incorporated into a realtime strategy game built on Torque Game Builder. We'll be testing at the minimum system specs that GarageGames recommends on Windows.
Windows Minimum: 500 MHz processor, 256 MB RAM, Windows 98, OpenGL or DirectX compatible accelerated 3D video card.
#2
02/14/2007 (7:42 pm)
Is this a problem that can be solved in one man-week or 12 man-weeks? Or to be concrete, how much would you charge to write this code and how long would it take you?
#3
1. Is the terrain strictly passable or impassable, or is there a variety of different passable terrains, some of which are easier to move over and some of which are harder?
I want to bias the villager movement to roads. To put in math speak, here's how to weight each edge: 0 = impassible, 1 = ok passible, 2 = road surface. So grassy open areas can have a weight of one but I definitely want to bias traffic for the routes.
2. Does the terrain change at all over the course of a game?
Not yet. But we should account for that later on, that will be a good way to show improvement in infrastructure, showing roads become more traversable connecting remote parts of the map better.
3. The map looks tile-based. Is villager movement tile-based or
point-based? And if it's point based, what are the points per tile
and the type of the number (floating point or integer, I imagine).
All movement, player and villager movement is tile based like Warcraft. Point based would be too painful and unnecessary.
4. Are villagers always trying to navigate to one specific tile at a
time, or could they be trying to navigate to any one of a variety of
tiles? (For example, maybe they want to get to any of the nearest
points along a river or maybe just to a specific point along the
river.)
I haven't designed anything yet to have multi-tile destinations, but we should probably add that. An important example is imagine a villager walking up to a building, the destination for the villager is essentially all 8 nodes surrounding the building.
02/14/2007 (7:46 pm)
Also I should share some great questions about the pathfinding asked in a email conversation:1. Is the terrain strictly passable or impassable, or is there a variety of different passable terrains, some of which are easier to move over and some of which are harder?
I want to bias the villager movement to roads. To put in math speak, here's how to weight each edge: 0 = impassible, 1 = ok passible, 2 = road surface. So grassy open areas can have a weight of one but I definitely want to bias traffic for the routes.
2. Does the terrain change at all over the course of a game?
Not yet. But we should account for that later on, that will be a good way to show improvement in infrastructure, showing roads become more traversable connecting remote parts of the map better.
3. The map looks tile-based. Is villager movement tile-based or
point-based? And if it's point based, what are the points per tile
and the type of the number (floating point or integer, I imagine).
All movement, player and villager movement is tile based like Warcraft. Point based would be too painful and unnecessary.
4. Are villagers always trying to navigate to one specific tile at a
time, or could they be trying to navigate to any one of a variety of
tiles? (For example, maybe they want to get to any of the nearest
points along a river or maybe just to a specific point along the
river.)
I haven't designed anything yet to have multi-tile destinations, but we should probably add that. An important example is imagine a villager walking up to a building, the destination for the villager is essentially all 8 nodes surrounding the building.
#4
02/14/2007 (8:47 pm)
Deleted
#5
02/14/2007 (9:16 pm)
Wow. I should have had this conversation 4 months ago. Lee do you have an example of a really well done spec/requirements list? That's how this project has been going. No matter how detailed I think the reqs are, there always seems to be another order of magnitude more detail to define. And that's true for the artwork and code.
#6
Danged if I know how to spec something out for an artist though...I get kinda scared thinking about it.
02/14/2007 (9:49 pm)
Just make it as detailed as possible, and do it in several revisions where you've had time to sleep on it for a bit. I can never be perfect or detailed enough, but you can get it to where only a few intelligent questions are necessary from a developer.Danged if I know how to spec something out for an artist though...I get kinda scared thinking about it.
#7
02/16/2007 (3:37 pm)
What I've done in the past just allow one pass through the A* algorithm, this will mean that the npc may take a few frames to find its path completely, but it can me moving randomly until it's path is found.
#8
We need to create a lightweight pathfinding algorithm to support 100 villagers running around on one map that ranges in size from 64x64 tiles to 128x128 tiles. This pathfinding algorithm should be written in C, or C++. The map on which villagers are moving contains heavily trafficked routes as well as completely untrafficked areas such as river or forest. The AI should be able to handle basic collision between two villagers and reroute them efficiently. A typical map will have a town center which is a very common destination for the villagers and 20 to 80 huts which are another common destination but more spread out. The edges of the map do not wrap around like PAC-man. The map just ends there. The villagers can move in 8 directions only. up, down, left, right and the 4 diagonals in between.
Further requirements:
1. For weighting tiles on ease of traversing, use the scheme: 0 = impassible, 5 = open grassland, 10 = well-paved road. Conditions of a tile can change over time, for example dirt roads (6) can be improved to well-paved roads (10).
2. Destinations for some paths are multiple tiles. For example, a villager can complete a walk to Kickstart store by arriving at any tile adjacent to the Kickstart store.
3. Pathfinding has to allow for interruptions. For example, the player avatar can walk up to a villager and the villager must stop to converse and then resume walking after the conversation.
This code will be incorporated into a realtime strategy game built on Torque Game Builder. We'll be testing at the minimum system specs that GarageGames recommends on Windows.
Windows Minimum: 500 MHz processor, 256 MB RAM, Windows 98, OpenGL or DirectX compatible accelerated 3D video card.
Here is a sample map where villagers will often be walking:
Click here for more sample map and artwork.
02/19/2007 (2:03 pm)
Here is a revised version of the AI Pathfinding Write Up based the great feedback I got recently. This removes many of the ambiguities from before:We need to create a lightweight pathfinding algorithm to support 100 villagers running around on one map that ranges in size from 64x64 tiles to 128x128 tiles. This pathfinding algorithm should be written in C, or C++. The map on which villagers are moving contains heavily trafficked routes as well as completely untrafficked areas such as river or forest. The AI should be able to handle basic collision between two villagers and reroute them efficiently. A typical map will have a town center which is a very common destination for the villagers and 20 to 80 huts which are another common destination but more spread out. The edges of the map do not wrap around like PAC-man. The map just ends there. The villagers can move in 8 directions only. up, down, left, right and the 4 diagonals in between.
Further requirements:
1. For weighting tiles on ease of traversing, use the scheme: 0 = impassible, 5 = open grassland, 10 = well-paved road. Conditions of a tile can change over time, for example dirt roads (6) can be improved to well-paved roads (10).
2. Destinations for some paths are multiple tiles. For example, a villager can complete a walk to Kickstart store by arriving at any tile adjacent to the Kickstart store.
3. Pathfinding has to allow for interruptions. For example, the player avatar can walk up to a villager and the villager must stop to converse and then resume walking after the conversation.
This code will be incorporated into a realtime strategy game built on Torque Game Builder. We'll be testing at the minimum system specs that GarageGames recommends on Windows.
Windows Minimum: 500 MHz processor, 256 MB RAM, Windows 98, OpenGL or DirectX compatible accelerated 3D video card.
Here is a sample map where villagers will often be walking:
Click here for more sample map and artwork. 
Torque Owner Lee Latham
Default Studio Name
I'm reminded of the engineering/software development truism--"you can have it done Good, Fast, or Cheap. Pick Two". Which two you pick depends on your situation...sorry if I'm not understanding your question properly.