Hacker News Reader

Comment by socialist_coder | Hacker News Reader

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

View on HN

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.

Ah, makes sense. Thank you!

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.

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.

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.

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.

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 :)

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

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.

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.

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.

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

That's funny, I understand it as the exact opposite. The fox is tasked with finding the shortest path that hits 100 points. This leads it to the closest high point density area.

But the whole point is that the fox doesn't know actual distance, it only knows triangle distance.

Yeah, I think the the path length is calculated in terms of distance, but the patching requirement isn't a set distance.

> The fox is tasked with finding the shortest path that hits 100 points.

This is exactly what I said (breadth-first). Breadth first find shortest distances to all nodes in the neighbourhood.

> looking for the longest path

> "The Fox isn't trying to get 100 meters away - it's trying to get 100 triangles away."

Breadth-first search wouldn't be possible. If at each triangle the fox has ~2 options that's 2^100 to get to 100 triangles away

But if it did impossibly work out every journey, and then chose a random last node it would end up in camps more often.

Depth-first search shouldn't preference the camps, unless it gets dragged in from afar. But if it can only get dragged in really close to/in a camp, then it's about the same probability as the fox running past/through a camp anyway. And I would assume as a player you would see the fact it's pretty.

> If at each triangle the fox has ~2 options that's 2^100 to get to 100 triangles away

I don’t think you understand what Djikstra’s algorithm is. Breadth first doesn’t mean you have to always re-visit the same node more than once.

Hindsight is 20/20

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.

Reply on news.ycombinator.com