6 ms·

> The Fox isn't trying to get 100 meters away - it's trying to get 100 triangles away. Maybe this is obvious but I'm not seeing it... Why would an NPC measure

> The Fox isn't trying to get 100 meters away - it's trying to get 100 triangles away. Maybe this is obvious but I'm not seeing it... Why would an NPC measure distance in triangles instead of meters? Why is it trying to get 100 triangles away?

deleted 5y ago
[deleted]
korijn 5y ago
To avoid the conversion (and more complicated path finding algorithm) and use less cpu, I would think. Game dev is all about the cpu budget in order to achieve a target frame rate.
- kevingadd 5y ago
  In particular if you're doing pathing for tons of npcs (as they are) you really want to keep that optimized. In Guild Wars at launch for one of our expansions we had huge CPU issues with our game servers - it turned out designers had laid down really long elaborate paths for NPCs like guards and townspeople and the server was calculating all those paths at once when players entered a new zone, so it was saturating the game server. I had to build an auditing tool so we could scan all the zones for long paths and replace them with simple ones. Bethesda has been building this specific type of game for decades so at this point things like npcs having complex patrols or other behavior is something they've figured out how to do well.
  - jeofken 5y ago
    I played a lot of Guild Wars when I was a teenager with my friends! We were very glad to have a MMO that was fun and had raids, even though we couldn’t afford the other ones with a monthly cost. It was also prettier than other games. I still remember many of the locations :)
hadlock 5y ago
Hindsight is 20/20
- foxpurple 5y ago
  Even looking back I don’t see why you would care. The fox runs away. The fact that it doesn’t run away to a perfect radius away is probably better.
jimminy 5y ago
The speed of computing a path from vertex to vertex is faster than trying to generate a point at X distance for the pathing object. So you give the NPC a speed, and it moves as far along the edges between vertexes in each time interval. The navmesh also helps keep the AI traveling in places that have been marked as safe for travel, without collision or drops.
- socialist_coder 5y ago
  Ah, makes sense. Thank you!
jayd16 5y ago
Easiest way to pick a valid random location is to pick the center of a nav triangle. They could have traversed the nav mesh counting distance instead of just triangles but I guess they didn't and it worked out fine for the game.
aaron695 5y ago
More interestingly , if it doesn't know meters then how does it know density, why would it pick a more dense section of triangles.
- thargor90 5y ago
  it doesn't know density. density is a property of the triangle placement. More triangles in "dense" areas. Pick a random triangle, you are likely to fall into a dense area.
- qqqwerty 5y ago
  The twitter thread isn't super clear about the exact mechanics. But If I had to guess, maybe the fleeing fox randomly chooses the path to follow, and because there are more possible paths in the dense parts of the map the odds of selecting one of those is higher. i.e. if I have 6 possible paths to my right, two to my front, and two to my left, if I randomly pick a path there is a 60% change of going right.
  - aaron695 5y ago
    This only works if the camps mesh is really wide, black hole style. If you enter the camp and it gets high suddenly, nothing is changed, since as a player you know you are in a camp. The fact the fox stays, chewing through triangles, rather than running though like it would if it was based on meters doesn't matter. Although, since the fox stays in the camp, you would think it was telling you something, even though it was random chance.
    - heavenlyblue 5y ago
      As I understood that is that the fox is looking for the longest path (e.g. distance defined by breadth-first search) and longest paths are usually the ones that lead you to treasure because treasure is hidden deep within levels
      - s1artibartfast 5y ago
twic 5y ago
I wonder if this is just actually not true, but was a hamfisted way of explaining what was happening. In the low-density mesh which the fox uses, there are more nodes around treasure, and because edges connect nodes, more of the edges in uninteresting space lead towards treasure. So just by picking random edges, or edges away from the player, you are likely to end up near treasure. It's a bit like the is fox moving through a non-Euclidean space which has more volume near treasure. Because measuring distance by hops would be absolutely daft.

deleted 5y ago

[deleted]

korijn 5y ago

To avoid the conversion (and more complicated path finding algorithm) and use less cpu, I would think. Game dev is all about the cpu budget in order to achieve a target frame rate.

kevingadd 5y ago
In particular if you're doing pathing for tons of npcs (as they are) you really want to keep that optimized. In Guild Wars at launch for one of our expansions we had huge CPU issues with our game servers - it turned out designers had laid down really long elaborate paths for NPCs like guards and townspeople and the server was calculating all those paths at once when players entered a new zone, so it was saturating the game server. I had to build an auditing tool so we could scan all the zones for long paths and replace them with simple ones. Bethesda has been building this specific type of game for decades so at this point things like npcs having complex patrols or other behavior is something they've figured out how to do well.
- jeofken 5y ago
  I played a lot of Guild Wars when I was a teenager with my friends! We were very glad to have a MMO that was fun and had raids, even though we couldn’t afford the other ones with a monthly cost. It was also prettier than other games. I still remember many of the locations :)

hadlock 5y ago

Hindsight is 20/20

foxpurple 5y ago
Even looking back I don’t see why you would care. The fox runs away. The fact that it doesn’t run away to a perfect radius away is probably better.

jimminy 5y ago

The speed of computing a path from vertex to vertex is faster than trying to generate a point at X distance for the pathing object. So you give the NPC a speed, and it moves as far along the edges between vertexes in each time interval. The navmesh also helps keep the AI traveling in places that have been marked as safe for travel, without collision or drops.

socialist_coder 5y ago
Ah, makes sense. Thank you!

jayd16 5y ago

Easiest way to pick a valid random location is to pick the center of a nav triangle. They could have traversed the nav mesh counting distance instead of just triangles but I guess they didn't and it worked out fine for the game.

aaron695 5y ago

More interestingly , if it doesn't know meters then how does it know density, why would it pick a more dense section of triangles.

thargor90 5y ago
it doesn't know density. density is a property of the triangle placement. More triangles in "dense" areas. Pick a random triangle, you are likely to fall into a dense area.
qqqwerty 5y ago
The twitter thread isn't super clear about the exact mechanics. But If I had to guess, maybe the fleeing fox randomly chooses the path to follow, and because there are more possible paths in the dense parts of the map the odds of selecting one of those is higher. i.e. if I have 6 possible paths to my right, two to my front, and two to my left, if I randomly pick a path there is a 60% change of going right.
- aaron695 5y ago
  This only works if the camps mesh is really wide, black hole style. If you enter the camp and it gets high suddenly, nothing is changed, since as a player you know you are in a camp. The fact the fox stays, chewing through triangles, rather than running though like it would if it was based on meters doesn't matter. Although, since the fox stays in the camp, you would think it was telling you something, even though it was random chance.
  - heavenlyblue 5y ago
    As I understood that is that the fox is looking for the longest path (e.g. distance defined by breadth-first search) and longest paths are usually the ones that lead you to treasure because treasure is hidden deep within levels
    - s1artibartfast 5y ago

twic 5y ago

I wonder if this is just actually not true, but was a hamfisted way of explaining what was happening. In the low-density mesh which the fox uses, there are more nodes around treasure, and because edges connect nodes, more of the edges in uninteresting space lead towards treasure. So just by picking random edges, or edges away from the player, you are likely to end up near treasure. It's a bit like the is fox moving through a non-Euclidean space which has more volume near treasure. Because measuring distance by hops would be absolutely daft.