Optimization help

[signal sleet]

I made a simple system that allows the player to place objects into the world on a grid. However, for the project im working on this "grid" needs to be infinitely large. In order to not have a really large 2d matrix I created a list and whenever the player places an object it just get added to this list with the grid spots it occupies. Then when the player places a new object it has to loop through the whole list to make sure it doesn't match a spot that already has an object on it. However, as you already probably can tell this is not very fast. What should I do instead of this. I was thinking of making a matrix thats lets say 5x5 then if anything is placed outside of this matrix it just makes it bigger to fit. However, copying data into a new larger matrix anytime the player places an object I don't think it very fast (could be wrong). I saw some things on splitting the grid into chunks but then how do I quickly find the chunk the player is trying to place items in and the location in the grid the player is trying to place said item. (currently i am just using rounded mouse positions).

[sacred loom]

• split the world into chunks
• keep changes to the world in a two dimensional array, per chunk, no need to loop, just a simple array lookup
• only save changed chunks

you can then also save the chunks in a 2d array and just check:

Assumed chunk size 16x16:

var currentChunk = chunks[Mathf.FloorToInt(playerPosition.x / 16), Mathf.FloorToInt(playerPosition.y / 16)]

what i've also seen is hashing the coordinates of the object and storing all changes as
Dictionary<PositionHash, ChangeData>

which would also allow you a simple lookup based on the coordinate hash, but you need to make sure you have a hash function that gets you unique identifiers with little data

[signal sleet]

Im assuming for the chunk based approach I would need to do something like having 4 2d arrays for chunks. since if where the object is placed is negative it would try to get a negative index from the array. So, it would just check if no pos are negative use array 1, if just x pos is negative use array 2, ect.

[sacred loom]

yeah most likely, or set a realistic max worldsize and offset by that

[runic folio]

Any time you think performance, you should test and profile.

Assumptions are only gonna take you that far.

[random lynx]

For an infinite scale with a low density, the most optimal way would probably be to create some sort of Quad Tree implementation. Writing and reading operations would have log(n) speed.
For the easiest solution that is somewhat optimal, you can just create a Dictionary that takes the position as a key (or custom hash). The downside of such a solution is that in certain cases, hashes may overlap, but in an optimistic scenario, writing and reading operations would have almost instant speed.
I would suggest going with the second one, then optimize it at a later stage of the project if it happens to cause performance issues.