search

SnpM / LockstepFramework

Framework for lockstep RTS, TD, and MOBA games.
MIT License
1.39k stars 348 forks source link

Height-related path finding logic would be very useful #164

Closed futouyiba closed 5 years ago

futouyiba commented 5 years ago

Hi John, this is not a bug, it's a request. I think if the path-finding algorithm takes grid node height into account, it'll be very nice. My map is surrounded by mountains and hills, so the borders would be easily generated if we have this logic. In fact, Unity's built-in nav agent has a set of height logic when navigating. It can judge whether the height gap is too much, so the agent can't climb or get down. It's the fact I need determinstic that it could not be used. Is it conflict with our A star algorithm? Is it too much to implement? I'd be excited if I can hear your opinions on that : )

futouyiba commented 5 years ago

Here is what I've done: I let pathfinder.findrawpath() function judge the height gap. If the gap is too much, the fcost, gcost wouldn't be calculated at all. In this way, the findRawPath is correct, but it's wrong again after smoothPath. And, as I'm imagining... maybe height gap could be another cost ~ like a HeightCost = (grid1.gridHeight - grid2.gridHeight)^2.

futouyiba commented 5 years ago

As rethinking it, maybe the simple way is to judge the height map right from when we generate neighbor nodes. Nodes with too much height gap are just not connected. This way, it should solve the "smooth path" issue?

SnpM commented 5 years ago

Height-related pathfinding is a great idea. I will try to tackle this if I have time before the end of this month.