Tilemap with pathfinding. Best approach?

Unity Engine
,
1

Requirements:

  • 200x200 tile map with roads and buildings.
  • multiple heatmaps for all kinds of data (how pretty area is, how noisy, proximity to certain buildings, movement cost, etc)
  • Hundreds of roaming pathfinding agents with local avoidance and precalculated major path data, and dynamic local pathfinding.

What is the best data structure for this? I was thinking a singleton DynamicBuffer for each of these layers. (pathfinding cost (float) in one buffer, beauty heatmap (float) in another, etc)

Is that a good idea?

Should I worry about cache misses in 200x200 float dynamic buffer?

Would “1 tile = 1 entity” approach have some advantages or be better overall?

Thanks.

2

We have 400x400 map splitted by 40x40 locations, every location cache is 2 dynamic buffers (for every unique point in location request and for every unique node path request)

2 Likes
3

I’ve gone with a dynamic buffer for each data type for my map. So a buffer of height elements, a buffer of terrain types etc.

I’ve got hierarchical astar for high level pathing and flow fields or grid based astar for local searches working with this approach. Obviously the data structure of the map is just one part of the puzzle.

1 Like
4

Did you split it for more cache integrity or some other reasons? If for cache do you actually know if it made a difference?

Yeah, I think I have general idea of what I want and need to do but then there are probably a lot of detail I don’t see yet.

Thank you all for replies.

5

It’s for fastest pathfinding, of course it’s faster, in addition our navigation grid not static and with this splitting we can rebuild only part of graph. More info here:
https://discussions.unity.com/t/716170 page-2

1 Like
6

hello, can I ask about how you actually use dynamic buffers to do pathfinding? I’m new to ecs, and I found I can’t get dynamic buffer array in the current API. So I don’t know how to use buffers to save and read the map data properly. I’m also wondering which is better for keeping grid-based map data nativeHashMap?or dynamic buffers? If dynamic buffer works like list, then we can only get a grid unit’s data by buffer’s index? sorry for my poor English … Is so hard to find some dynamic buffers use case on the Internet.