search

roy-t / AStar

A fast 2D path finding library based on the A* algorithm. Works with both grids and graphs. Supports any .NET variant that supports .NETStandard 2.0 or higher. This library has no external dependencies. The library is licensed under the MIT license.
http://roy-t.nl
MIT License
340 stars 60 forks source link

Memory allocation #9

Closed gamemachine closed 6 years ago

gamemachine commented 6 years ago

I like the code overall, but it's not usable in games as is because it's so heavy with allocations.

Lots of games have a zero heap allocation policy for pathfinding.

roy-t commented 6 years ago

Hmm, the only allocations per frame are from making searchNodes, which are short-lived (g0) objects. I haven't had any problems. But we could move to zero allocations by using a pool for those objects. What do you think? Are you having real problems?

gamemachine commented 6 years ago

ToArray on the Stack allocates, as does just allocating a Stack so you allocate two collections there on every path. IEnumerable allocates also.

I'm using Unity which uses boehm. It's common practice to have zero gc in the Update loop on Unity because of that since short lived can easily end up in a stop the world collection.

No big deal I needed to customize it anyways for concurrent pathfinding also. I'm working with up to 100 agents pathfinding every couple of seconds. Which is too much for the main thread. I also converted it to use Unity Vector2Int instead of positon so I didn't need multiple position lists. Plus I just have the pathfinding specific stuff since Unity doesn't support .NET Standard (beta release does but not on that).