Storing a Map

[capturts]

For a game idea I need to store the map or world for characters to explore. If it was small I might just make a 2d array storing the contents of each location. But it will be big, hundreds of squares by hundreds. I think an SQL table with x coordinate,y coordinate and "content" (ie tree, building, whathaveyou). This should work fine, unless anyone has better suggestions? Every x,y coordinate in the 'world' will have a corresponding table row. If it's not there then it must be an out-of-bounds area. When my character is at location 50, 60 I can get the contents of all the locations from 45,55 to 55,65 (or whatever) then figure out which of those areas are 'visible' to the character - maybe the lake at 52,60 can't be seen as there is a hill at 51,60... then I can display the surrounding area for them to plan their next move.

Now the real problem, how do I store what the character has seen? as I walk from 50,60 westward towards 100,60 my character will see a great deal of stuff. The idea is that they will get an auto generated map of all they have seen, so they can look back and figure out the best route back to somewhere they need to get to, for example. I could have another table in the DB to store each location each player has seen. It'd need to store the x and y co-ords and the player id. But this table would get massive very quickly with multiple players all trekking through the map. Every move they made might add several rows to the table as they may see several squares in each direction from their location. And this would be multiplied by each player going through the area...

Any suggestions?

[133794m3r]

OK the first part of your question. Yes you're going to have to store it as a table inside of your database but I'm doing it a bit differently. Basically I have  "default" tile for every single map, when there is no tile data there, then the "default" tile goes in this area. This will allow you to save _tons_ of space inside of your database since most maps will have, no more than 50% of it filled with custom tiles beyond the standard "can pass through this" one. So it's a lot smaller.

Now onto your next one, I'd store it as a heat-map kind of thing. Have a table which holds the x, and y coordinate, and then also a number of times that someone has passed through it. Everytime that someone goes on a tile increase this value by one. This will then allow you to see how many people are using that particular path and thus you can easily see what's the highest amount of values.

Inside of your databases themselves, to try to reduce the overall size, I'd do what I said up above, and I'd also store not the tiles themselves but a reference to them inside of the database. Like a "tile-id". This will help you to reduce the overall size and will increase the amount of data that can be cached.

[Chris]

Map:
Make a default terrain (plains?) and insert into database only terrain that is not plains (in a traditional map it should let you reduce the DB size by 70-80%).
OR
Make it like Adom traps algorithm, depending on X,Y the different random stuff is generated (so it's a very cheap auto generated terrain). Generally, I recommend checking roguelikes if you are into anything related to generated terrain.
For example I would make default terrain desert, then auto generate cactuses using x,y seed and only the rest I would put into DB.


Visited:
Store it in bits not bytes (you need 0-1 value only). I would add separate table rows for each 100x100 area player has been at least one, bitfield field type (1 byte=8 grids, so 100x100 would require 10kb), possibly gzipping the bitfield of the non current area (normal plains map will compress very well, so you might go below 1kb per 100x100).

[capturts]

Thanks, you've given me some ideas to look into. I'd not really meant a 'heat' map, but I guess it'd be quite an interesting feature to consider.

I'm still worried that the amount of data will get out of control. I was looking into html 5 local storage and wondered if I could just use that to store the explored areas a character has been to. It seems a little limited as it is just key/value pairs, but maybe the data could be manipulated in a clever way to fit it in to this paradigm. The problem being that if someone logs into the game on a different computer or even a different browser then all the data will be lost... Maybe the data could be uploaded periodically to the server?

[133794m3r]

Woops, I was missreading what you've said to someone. Well then why not just make it a "map". and subdivide your areas into groups. Like areas of 10x10 tiles or something similar. With that in mind you can say "oh you explored this" whenever they enter anywhere on that 10x10 area grid. With this in mind, you should store the person as having seen "this" area. And then they can see that part of the map.

[Chris]

One more thing, visibility map will be highly regular (big hunks of 0 and big of 1), because players hate leaving any unexplored "dots" on their way. This compress extremelly well.

Code: [Select]

$str=''; for($n=1;$n<=100;$n++) for($y=1;$y<=10;$y++) $str.='1110011111';

$compressed = gzcompress($str, 1);
echo $compressed;
echo"<br>";
echo "Raw: ".strlen($str)." ";
echo "Compressed: ".strlen($compressed)." ";Results in: Raw: 10000 Compressed: 94  (that's 99% decrease of data size!)
Note also that I used compression level 1, which is the lowest and the fastest compression possible (with 9 you can go for 99,5% reduction).

[capturts]

That is a good point that I may not have to store every location, as you point out you can 'see' a certain distance (I'm thinking 5 squares each way (but that's fairly arbitrary) so I only need to store 'the furthest square they've been to'.

That's also quite interesting with compressing all the bits. How would you store the compressed data in a DB, just a 'blob' field?

[Chris]

Actually, if there is compression it should not matter if these are bits or bytes, so I would go for simple MEDIUMTEXT (for 100x100 area).