Blog 3: World Organization

3/14/2023

Welcome back to the Integration Hell development blog. Also, happy pi day.

As the title states, this blog is mostly about how the world is stored in memory during gameplay. Making the game world "infinite" poses challenges for holding the game world. I have decided that the world is a square made up of 4294967296 x 4294967296 sectors, which is very large. The issue with a world this size is that it is not feasible to fully generate one in a reasonable amount of time and it would take up more memory than most computers have.

One of the most important things for me was to try to keep the access time to a sector to be constant regardless of how large the world is. My current implementation of the sector storage is almost has constant access time. The sector storage system consists of two arraylists. The first array contains the sectors, and has O(1) access time. This is because each sector has an xy pair for its location an this array stores sectors in row major column so any index to a sector can be reliably calculated and requires no searching. Row major column works perfectly with a square grid but has some issues with nonsquare maps. The world maps in IH are not guaranteed to be square since the player is free to explore the world how they want. For example, they could just go straight up if they wanted. I did come up with a solution that still allows me to use row major column at a small penalty.

Chaotic Sectors - Some sectors will not fit into the sector array in the row major column system since they may be outside of the square that is the array. I labeled any sector that fits this description as a "chaotic sector". When trying to store a chaotic sector, the game looks for a unused section of the row major column and places it there. It also stores the xy coordinates and the index it's stored in the second array. When the game tries to find a chaotic sector, it looks in the second array to find the xy coordinates of the sector and uses the index next to those coordinates to retrieve the sector. When the game has to retrieve a chaotic sector, using the chaotic array is not O(1) time but O(n) time since the array has to be searched until the sector is found. However, this chaotic array will always be smaller than the row major column array since not every sector generated will be a chaotic sector, and as the world size approaches the maximum size the number of chaotic sectors will approach 0 since more of the sectors will fit into the array in the proper spot. Also, while making the arraylists larger may lag the game for a frame or two, this will only happen at most 29 times. There are still two issues I haven't addressed yet in this blog that I will put in the next paragraph.

Problem 1 - When a chaotic sector is generated, it goes into an empty spot in the row major column arraylist. What happens if we now want to generate the sector that is supposed to go into that spot? The answer is simple, we kick the chaotic sector out of that index and move it to a new one. (I realized my implementation of this was bugged when I wrote this part of the blog).

Problem 2 - What about negative coordinates? If the player spawns at 0,0 then they should be able to move in all four directions. However, arrays do not play nice with negative numbers so I didn't use any for the coordinates. Instead, the player will spawn in the center of the map, which is defined as 2,147,483,468 , 2,147,483,468. Now they can move in all four directions and not need negative numbers.

Now that world generation is possible, I now need to be able to load worlds from disk and be able to render worlds to the screen.

The Checklist:

Tasks:

𐄂 Put an image on the window

𐄂 Render a tile from memory

𐄂 Render a sector from memory

𐄂 Render the game world

✔️ Have the program make the world

𐄂 Load world data to disk

✔️ Save world data to disk

𐄂 Create simple assets to use for the game