Maps "map blocks"

[Fizzadar]

I currently have a nice map system with two tables, one for your map info (background image, name, etc) and the other is a list of "blocks" which form the map (like, no-move blocks or change-map blocks or people blocks) and so on.

Anyway, the problem comes when I want to make lots of similar styled maps, do I use the current system, and simply copy the blocks for each map (means a large blocks table, not a problem?) or something else?

My other plan was to convert the map block data to arrays and stick it in php files, each map is just a simple php file of data, to increase speed, since I don't need to edit them much, plus I could just copy the files for different block layouts/maps.

The reason this all happens is because I have main big maps, which is fine, but I want lots of houses within these maps, and they all need to be very much independent of each other, although many will use the same basic template.

Advice? 

[Soul]

This is an interesting question I'm currently facing in my own project as well

My first implementation had map tile data persisted to the datastore. This meant for every tile in the map, there was a corresponding model instance. Every time a character moved, data for all tiles in view had to be read from the datastore.

Later I moved tile data to static arrays as I figured I didn't really need an instance for every tile if tile states weren't going to be altered dynamically. Non-static entities such as user characters, buildings, mobs are stored together with coordinates, and this is the only data that needs to be read from the datastore.

The 2nd implementation is much faster, so I'm hoping it will be sufficient for my needs. I'd be interested to learn about better ways to do this.

[saljutin]

Map:
1. Lesson: if you have big table with map tiles DON'T choose them like: "SELECT .... WHERE x=$x AND y=$y", so lets say grid 3x3 would need 9 queries with both X and Y selection
1. Primer: I had table with 1002001 rows and map 9x9, it was loading like 30 seconds

2. Lesson: try to select ALL visible map from that table in 1 query like: "SELECT .... WHERE (x>$xmin AND x<$xmax) AND (y>$ymin AND y<$ymax)"
2. Primer: same table, method used as above loading time was about 10 seconds (if I remember)

3. Lesson: get rid of X and Y, rather create some function like: ID = f(X,Y) and then use such query: "SELECT .... WHERE id=f(X,Y)"
3. Primer: I used this query: "SELECT .... WHERE `id` BETWEEN $id1s AND $id1e OR `id` BETWEEN $id2s AND $id2e OR `id` BETWEEN $id3s AND $id3e"
for 3x3 local map, also this is the ID GRID
3 6 9
2 5 8
1 4 7

so ID 1 = X 1, Y 1
ID 9 = X 3, Y 3
now you must just create function which returns you such X or Y
loading time for such grid was like 0.05 seconds, with added UNITS, CITIES shown on map and BORDERS so more queries but faster

[codestryke]

Seems I've done a mix of everything above, the important thing for me was speed and to be able to create very large maps. This won't fit everyone's need so take what you can from it.

In our game you are on a grid (80x80), in that grid are corporations that you can go inside of. First problem was shear size with an 80x80 grid you are looking at a map file that contains 6,400 entries. Even with a moderate number of people playing and the table indexed it's still give the poor database quite a work out. Since the tile that shows the grid is the same everywhere it wasn't necessary to store those items in the database. So no instead of 6,400 entries in the database we only store where the corps are which is a table that consists of 200 entries. With only 200 entries and the database having a combined index on the X/Y coordinates it's blazingly fast

Once you are in a the corp, the data in the corp table takes over. That table is a bit bigger with just over 11k entries. We placed a index on the corpid and another combined index on X/Y. Since the first index narrows the first subset then applies the x/y it's pretty quick.

The method for the query is similar to what saljutin posted above in #2. With 20+ players online the query speed was still less then .005. We didn't go with his option #3 because people don't comprehend maps going from bottom to top per column. Our map coordinates are displayed to the user so we needed to make it as understandable and natural as possible. I say this because in an RPG style game displaying those coordinates might not be an issue.

The nice thing about this approach is it's very expandable. I could create more "worlds" just by adding a worldid to the main map and adding worldid to the corp table then combined index on worldid + corpdid. Another way would be to make another set of tables and add the worldid to the table names (haven't tried this approach yet).

For me personally I tend to stay away from storing things in text files as they become burdensome to manipulate down the road. Nor do I like to store serialized data in the database for the same reason. It all needs to be fast and it needs to be easy to work with down the road and I will sacrifice a bit of speed to make it easier for someone to manage down the road.

[saljutin]

that #3 is only solution how to show map. maybe I cannot really explain it
X-Y style
(1,3) (2,3) (3,3)
(1,2) (2,2) (3,2)
(1,1) (2,1) (3,1)

ID style
3 6 9
2 5 8
1 4 7

this is the same, so you CAN always show people X and Y coordinate, BUT everything what you show and select is only by choosing appropriate IDs from table rather then x=... and y=...
so lets say this 3x3 is global map and you want to select 2x2 area local to show to user.
X-Y: "SELECT ... WHERE (x>=2 AND x<=3) AND (y>=2 AND y<=3)
ID: "SELECT ... WHERE `id` BETWEEN 5 AND 6 OR `id` BETWEEN 8 AND 9

both selects same map "slot" and you can show that. problem is that this formula to get ID from x and Y is limited...in this primer you cannot extend this map in Y direction because it will screw your positions, e.g. 4 will be up from 3 but if you decide to have map which is fixed and does not grow - I had map 1001x1001 global, and I showed 9x9 in 0.05seconds. I showed not only map but cities and borders and units too!
So I still think this is the best solution IF your map dimensions are fixed OR if you only "grow" it in one direction.

make a contest where you have 100x100 map and you must show 7x7 pieces from this map and lets calculate time needed (and resources) with other ways and my way if u wish

[codestryke]

As I said in my post the way I did it isn't going to fit every ones needs. Let me use my limited knowledge of your game as an example. I say limited because maybe you are doing more behind the scenes

Your game is in space and at certain x/y coordinates you have a planet. If your world is 1000x1000 you don't need an entry for every tile, the only thing in the database that needs to be there is the x/y coordinate of the planets, which will be an extremely smaller number. Say the 1000x1000 universe has a population of planets that's 20% which comes out to 200,000 entries. So with my method you are only quering a table with 200,000 rather then a table with 1 million.

Maybe you are doing that and using your approach with the ID's as well, if that's the case I can see where yours could be faster. As mentioned above I'm only polling a table with 200 records in it, with that little amount I don't see where either way is going to be that much faster then the other.

As for resources if you are pulling 9x9 grid then you are going to be using more then I. In a 9x9 grid I will probably only have maybe 1-10 entries in the recordset tops vs your 81. This recordset is then returned to the browser via JSON and the browser does the rendering of the grid. All the backend does for my game is send JSON text back to the browser when you are in the map part of the game.

I won't argue that your method is faster when it comes to getting coordinates out of a table when you have an entry for each tile in the map, what I did offer was a way to think about storing the data and getting rid of the dead space if that approach would work for someone.

[Nox]

#3 I can't really see how could be better to use a function to calculate some 3rd value from coordinates than have it done naturally with X, Y and index on (X+Y)
I'm not sure if MySQL is even able to cache and optimize queries with functions
...but of course feel free to prove me wrong

[Fizzadar]

I'm not loading every block, I'm using background images to "draw" the maps, literally all I'm doing is when you load a map, it load up all the move blocks (just by ID, each map has 933 blocks which count horizontally in 21 rows) and it just displays them. When you move, it checks for any blocks in the place your moving to (so a tiny select from blocks where block_id = moveid) etc, if there's like a no-move, you get blocked.

My problem is when I'm making the same map over and over, I'll just fill up the database will billions of the same block combinations. Although I'm considering moving to arrays now to keep it blazing.

[saljutin]

@codestryke - no it wasn't space game it was game where I actually needed all squares in DB because each tile was "producing" different number of resources if user captured it so 1002001 table entries

@Nox - make such table with 1mio+ rows and try your way, indexing and all (I tried everything but it is too many entries so its slow)

[codestryke]

As this topic has come up numerous times and in the interest of science I started doing some actual testing. I did the test first with a 100x100 grid, I'm currently waiting for my table to fill with a 500x500 grid. I'm not absolutely sure that the 100x100 grid wasn't being completly cached into memory so I went bigger

After looking at saljutin's post again I noticed that lesson #2 used Xmin and Xmax and lesson #3 used between so that got me thinking, is between faster then doing the ands?

Table was created with three fields x, y and tileid. All the tileid's were set to 1, a primary index was put on the x and y column.

With query caching turned off I executed 1000 loops, withing the loop I randomized and X and Y value and passed that to the query. The query then returned a 9x9 result set. So far the test results are:

XY test average (1000 runs): 0.00033727025985718
XY between test average (1000 runs): 0.00021153926849365

I've got to get off to work and will post the results of the 500x500 grid as well as the code I used to produce the results. If someone would like to add to the code saljutin's coordinate system and rerun the tests to compare that would be great, but in the mean time it looks as if using between is much faster then AND's

[Nox]

@saljutin
Em...I didn't mean it the way "who's winner and who's loser", just wanted the same as everyone - a good solution

I'm not sure how much you plan to change the map, someone here said the table data mostly won't change so indexes would only speed it up

But anyway - maybe I just don't understand what you meant -  is it about having 1 indexed column instead of pair?
You know, I'm a bit afraid of functions as ...well ok, I already wrote it...
http://www.mysqlperformanceblog.com/2009/01/23/optimizing-repeated-subexpressions-in-mysql/
I'm not 100% sure it's related but you can see, that mysql had a hard time optimizing the first query due to use of function, although the same every time

Ad cachability - did you test the speed over more requests on particular place (testing cache)?... I mean - if the first would take 5times more but the rest would take half then it would be imho better, but maybe it changes often so it wouldn't be useful that frequently, don't know

@codestryke
Nice test, now I look forward to #3 solution

Well...the cache is active in real action however, so I'm not sure it wouldn't be inappropriate to run a test with cache ON for reasons I mentioned above

Edit: you're welcome

[codestryke]

As promised here is the code for the map test I ran.

create-world.php will create a 500x500 grid
maptest.php will run both the tests and display the results
xcdb.lib.php I'm using my own db wrapper, I updated it so only starts the microtimer just before executing the query and finishes on the next line after the query. This way we are only comparing query execution speed.

With a 500x500 grid I got the following results:
XY test average (10000 runs): 0.00016485514640808
XY between test average (10000 runs): 9.6878552436829E-5

It seems the true speed is in two parts:
1. putting a primary combined key on X/Y
2. using between rather then (Xmin and Xmax) and (Ymin and Ymax)

This does not show results for what saljutin proposed in his lesson number 3, however, with numbers above being so low I don't think it matters much either way.

[codestryke]

Always good to release the code when comparing performance data Nox found an error in the XY test, which produced bogus values. A new version of the test is attached With the fix now added it really shows how much faster using between is then using ANDs.

XY test average (500 runs): 0.011800593852997
XY between test average (500 runs): 9.4476699829102E-5

Nice find Nox, thanks

[Basti]

Hi,
I have a table with x and y coordinates of the locations (player cities, empty tiles don't have an entry), but I don't know how to bring that informations on the screen. I want to use php. Can you give me some hints?
I thought about a pointer, which is located in the center of the map. When the player moves the map section northwards,the pointer changes to x and y+1. But how do i fill the fields around the center (pointerfield)?

[Chris]

echo $playerx-1,$playery.'<br>';
echo $playerx,$playery-1.'<br>';
echo $playerx,$playery.'<br>'; // centre
echo $playerx+1,$playery.'<br>';
echo $playerx,$playery+1.'<br>';

OR

for($y=$starty;$y<=$starty+$viewsize;$y++)
for($x=$startx;$x<=$startx+$viewsize;$x++)
{
if($x<0 || $y<0 || $x>$mapsize || $y>$mapsize) echo"[?,?]";
else echo "[$x,$y]";
}