....connections to its adjacent grid nodes in just a single byte!

from:
https://arongranberg.com/astar/docs/usingnodes.html#node-properties

“Each node stores which other nodes it is connected to. How this is represented depends on the graph. Grid graphs for example take advantage of its grid structure and can store all connections to its adjacent grid nodes in just a single byte!”

when I was trying to make a super fast grid based LoS, I was playing with this, I think. Basically 8 bits and a bit mask, with each bit representing SW, to S to SE to W to E to NW to N to NE (that’s how I structured it, since i build my terrain and other meshes the same way, bottom left to upper right “z* width + x”) I was marking each adjacent point as higher than eyelevel (1) or not (0). I never really got it to work.

But as far as I understand it, the CPU converts Bytes to Ints at runtime, and so this ends up being an extra cycle, and costing extra time, and only useful in memory saving for hard drive saving / serialization, but may actually hurt runtime performance.

If its true that Bytes do save on memory, do they save on runtime memory as well? Because I would love to go back to byte memory run things, if it would actually increase performance. (I dont like marking something with an int when a byte will do, because my maps are huge, and this game has a lot going on already, and it feels like a waste of 24 bits)

Hi

CPUs tend to be memory-bandwidth limited so bitpacking often makes sense just because they use less memory. This package uses bitpacking for a lot of things, not just connections. For example one bit is used for if the node is walkable, 8 for the connections, 8 for the graph index, 5 for the tag, etc.

However, it is often the case that other optimizations make more sense to do before this matters.

1 Like

Back to bitpacking for me then!