Algorithm to render (tiles, units, ...) to a tile based game map: data structure

[jannesiera]

I am creating a 2D top down tile-based game map with the HTML 5 canvas element. So that means I am using javascript to render data (like tiles, objects, unites, ...) to the canvas based map.

I already created a very basic demo: http://janne.siera.be/ . It will only work in Google Chrome and refresh once. I have a better version with smooth scrolling and the pre-loading issue fixed but that one isn't online yet. Now I'm going to extend this demo so I can prototype a game design ( it's called "General's Map" and you can read about it on my blog - http://www.bbgamedesign.com/ ). I'm not planning to create the best engine, because you can always improve those things and it isn't necessary for the prototype, but I would like it to have a good base for when I decide to go on with it after prototyping.

So right now I want to add extra "objects" to the game, like units or different buildings. You'll see that there are only "houses" in the demo. Well, I need help to create a solid data structure and algorithm to render that data. Keep this in mind:

     1. It can be specific for my game design, it doesn't have to be an engine for every one to use.
     2. It needs to be efficient, just because it's the absolute basics.

My data structure until now (take a look at the source code for better understanding):

I have one two dimensional array to create the map tiles called "myMap" with the rows and cols of the game map. That data holds which tile image needs to be rendered where. So basically that is all the info it holds.

I have another array called "objects" which hold the data of all the objects. Since They aren't relative to any tiles or anything I need to loop through the whole array to see which objects fit into the screen. This isn't desired since I can have up to 200 objects (buildings).

Now, what I need:

I need to render tiles, objects (like buildings and "waypoints") and units (like "armies" or "battle in progress icon" or anything I want). Tiles will be the base of the map, objects will be layered on top and units will be layered on top of objects. Units can only be on objects (they move from waypoint to building / other waypoint).

My proposal for a data structure and algorithm, but I am very unsure if it is a solid solution, that's why I need your opinion:

Have an array of tiles, like this:

Code: [Select]

var tiles = [tile0, tile1, tile2, tile3, tile4, tile5, ..., tileN];
and each "tile" is another array (so we have a two dimensional array). That array will have:

Code: [Select]

var tile0 = [img_id, obj_id, col_id, row_id];
img_id: A reference to the image.
obj_id: A reference to the object (if there is none, this is an empty string, or something like that)
col_id: The column this tile is in
row_id: The row this tile is in

(with column and row it should be easy to know where to render the tile)

The obj_id would be a reference for the "objects" array. This array included all objects, so if we know which tiles to render, we know which objects to render.

Code: [Select]

var objects = [obj0, obj1, obj2, obj3, ..., objN];
So like the tiles we have a two dimensional array again:

Code: [Select]

var obj0 = [img_id, events_id, width, height];
img_id: A reference to the image.
events_id: A reference to another array, the one which holds information about units etc.
width: the width of the object image
height: the height of the object image

The width and height of the object can be maximum 3x the width and height of a tile. I'll get back to that later.

I reference to an events array. Like we did before with the tile to objects too. I called it "events" instead of "units" because there can be different things going on (for example armies fighting, building in production, ... ) and we need to do the appropriate things. So the events array looks like this:

Code: [Select]

var events = [event1, event2, ..., eventN];
Each event here is an array which can hold different information and we probably need to do some checks on what to do but it provides a lot of flexibility.

For example:

Code: [Select]

var event1 = [type, img_id, param1, param2, ..., paramN]; // Can be ['unit', 20, bowmen, strenght=50, id=116]
var event2 = [type, img_id, param1, param2, ..., paramN]; // Can be ['under construction', 15, time=5000, id=23]
That makes up the data structure:

1. Tiles -> tile (reference to objects)
2. Objects -> object (reference to events)
3. Events -> event (do specific stuff)

Now the algorithm to render everything correctly. I wonder if it won't take to much resources and time to go through all these arrays and stuff?! :

- Loop through the tiles we need to display (the ones which fit into the screen + on extra row and column on each side for when there are objects on them (bigger than the tile size, that's why objects can be maximum 3x the size, visualization example)
- Draw each tile
- If there is an object -> add it's id to an array (like: "objectsToRender")

- Loop through the "objectsToRender" array
- Draw the objects
- If there are events -> add the id to an array (like: "eventsToRender")

- Loop through "eventsToRender"
- do stuff for each events


I did my best explaining everything but it's not easy. So if there is anything unclear please ask, I'll be happy to clarify. I would really appreciate it if you could help me finding a good solution.

[Sim]

very nice. exactly how I did it in visual basic 6 =)

i didnt see no questions though. was there suppose to be one?

[jannesiera]

very nice. exactly how I did it in visual basic 6 =)

i didnt see no questions though. was there suppose to be one?

The question is if this is a good solution or if I should use another, more effective, method .

[Marek]

From my limited knowledge of tile-based rendering, I think this is precisely the best way to do it. There is no way to get around the extensive looping.

The only optimization possible would be limiting the amount of tile/object data loaded, by loading a limited amount at a time from the server. But that might not necessarily help with performance, because the client-side is magnitudes faster than doing multiple HTTP requests.

I see you're using Dan Cook's tileset. What a great set of graphics.

[lolninja]

Hey, they way I do my 2d tile rendering is slightly different, rather than storing the tiles coordinate in the data section, I use a 2D array, which contains my whole map. so I have a block kind of like...

Code: [Select]

array
  0 =>
    array
      0 =>
        object(Obj)[1]
      1 =>
        object(Obj)[2]
      2 =>
        object(Obj)[3]
  1 =>
    array
      0 =>
        object(Obj)[4]
      1 =>
        object(Obj)[5]
      2 =>
        object(Obj)[6]
  2 =>
    array
      0 =>
        object(Obj)[7]
      1 =>
        object(Obj)[8]
      2 =>
        object(Obj)[9]

The reasoning being this is that I can have a loop that looks like...

Code: [Select]

foreach ($data as $colId=> $row) {
    foreach ($row as $rowId=> $cell){
       $cell->drawAt($colId*$width, $rowId*$height);
    }
}

But to be honest I think the result is pretty much the same, the only reason I use this kind of method is that is ports nicely into javaScript, where running quick is pretty important, as I was working on a JavaScript map renderer.

And my mapping information is pre-rendered into text files(the html, or json), so I can just include them server side and I have a map, then I can layer on my buildings and I have a nice complex map with pretty much zero server effort

But meh, I've given up far to many times to be dishing out advice. Its a tricky topic area, as imho your going to need to stream json data down to the client, as generating and transmitting the html will nuke any bandwidth you have. Before going heavy Javascript I had a working server/client using code based on http://horrain.com/iso/, but the problem was when developing locally it worked fine, as soon as I uploaded my code to my web server it just fell over.

But then you run into issues where your having to slow down the players interaction with the game client, so that it has time to process the json into html and render it. Also you have issues with compatibility with multiple browsers :S

With my Javascript heavy version that I was working on a few months back, I was processing mapping data into tiny json files, which had maybe 20x20 mapping elements, these were then rendered by the client into images using canvas, then simply moved around the dom using jQuery's animate functions, this method proved to work pretty well, but wouldn't work at all well in IE

Sorry if I come across as being negative, its just a crazy complex problem, and I'm yet to find a super sexh solution that doesn't require a RIA like Flash or SilverLight.

Also its worth using some OOP, as you can enclose your rendering code into your tile, allowing you to easily extend it, making it easier to render multiple images in one tile.

[JGadrow]

I would think you could use a structure like:

Code: (php) [Select]

$map = array
(
    0    => array
    (
        0 => array
        (
            'tile'    => 'grass.jpg',
            'objects' => array (...),
            'units'   => array (...),
        ),
        1 => array
        (
            ...
        ),
        ...
    ),
    1 => array
    (
        ...
    ),
    ...
);
In this manner, your coordinates actually store the data of: What tile represents this coordinate? What objects and units are here?

Then, all you ever need to do is determine which coordinates you're displaying and loop through those coordinates' objects and units for rendering.

This structure represents the map in a meaningful manner and eliminates unnecessary processing cycles. You would use a 2-dimensional array as the base of the map because you specified it was a 2D map. Obviously, you could create a 3D map by adding an extra array before processing tile, objects, and units.

*edit - stupid tab to space conversion always messing with my formatting! lol

[jannesiera]

Thanks for the replies. I seem to have forgotten to add the files in an attachment, so if anybody needs them for anything I will add them. Going to open source it as soon as I have commented better anyway (the version until now that is).

I think JGadrow's technique suits me best. Now gotta implement it .

[codestryke]

Transversing though the array, once it's created, is blazing fast. Actually, there is nothing faster then looking up and pulling data that is already in memory. The problem that occurs is PHP is not a static application that can hold that data in memory, each request must re-create that array which is what takes time. Memcache may help but I'm not that well versed in it so I can't really say it will or it won't.

An application now you have to start thinking application scope, not page, which isn't what PHP is designed for. The application needs to be created in memory and kept running so it can put map, item and such data into memory ONCE and have the clients talk to it, basically you are talking a server. Can you do this, yes, but performance will suffer as lolninja has related in his post.

You may want to check out this demo http://www.ape-project.org/demos/7/mmorpg.html. The demo recommends using Chrome as it has a faster JS engine.

For tile rendering http://www.gamedev.net/ use to have some really good articles on this subject.

[bbgames]

Memcached would be great for storing the array, if you're interested in caching things - as long as you can convert it to a string, you can store it in memcached.

[Chris]

As codestryke said, client side performance is basicly irrelevant (it will be fast enough). The problem is retrieval data from server.

I would use AJAX as a persistent storage of non changing data (background) and retrieve only "next row in the map scrolling direction" (part of background) and all dynamic objects (units).
Another trick is to store in database only non basic background tile (would work best if you have desert with a few cactuses ), everything not found is considered a basic tile (you could even use different gfx versions of non existant tile using X,Y as tile style identifier).

[lolninja]

I can't stress enough how important it is to pre-process your mapping data, getting any kind of coordinate data from the database will nuke any performance, imaging a 20x20 block of terrain data, that the user has to download every time they look at there home city, thats 400 rows of database information.

If you store that information in serialized text files then loading them into memory and unserializing is sooo much faster than any database access. Then you can grab the dynamic information from the database and render all the happiness.
That is if your shooting for complex maps, if your wanting pretty simple maps then it may not be to much of a memory hog.

To be safe its worth doing some experiments, write a quick dirty script that executes your current map rendering code, that basically loops a few thousand times, keep an eye on the server load and if you see it running out of memory or it makes your server cry, then its worth dumping the data you get from your database into serialized text files and retesting.

With my http://demo.httpmmo.com/mappy/ code I notice a huge difference in speed and resource usage. It also means I can have silly huge maps with very low load on my server, as the client is basically doing all the work

If I get some time over the weekend I may write some demo code to exemplify what I mean, as it took me a while to figure out how to do it nicely.

[JGadrow]

Don't forget, you can serialize data into a database as well as into files. But, yes, I would think that the base map (structure + tiles) should be stored in some sort of static cache. Maps have a finite number of views that will be applied to them, so it's possible to store every view ahead of time so that the only bit of time needed to add elements to the array are those items that change. Definitely units, maybe buildings depending on how your map works. Are building destructible? Then you can't cache them. If once a building is built it remains permanently on the map, you can cache any current buildings when loading a map. In this manner, you only need to retrieve any new buildings making the data loading faster.

I hope that clearly enough described... I have my doubts. lol

[jannesiera]

My plan is to get all the data from the database on page load and put them into a javascript multidimensiolan array (I converted the one JGadrow proposed from php to javascript) or other arrays.

Since I won't need to update data every time (my game is tick based, with one tick in 24h or so) I can just use that data through the game. The game will only be played on a map with one "area" (a <div> or so) besides it. When I get user input I do an AJAX call if needed (I pass on an id and get additional data for a building, for example). Obviously I won't have to do an AJAX call when scrolling the map or anything .

I am a bit concerned with security though. I'm not really a programming expert or anything and that is something I know little about. One thing that I'm certainly going to do is check all input on the server side. For example does a certain action I will check if that action is possible etc.

Anyway, firstly I need a prototype. So server load / speed / security are not a priority. It's only when I'm certain I'm going through with it that I'll have to change and improve the code, but going in the right direction already won't hurt either .

All your input is really appreciated and I will use it as a resource in further development. Also others will certainly find this topic useful!

[mobeamer]

Just a thought...and I didn't catch what your backengine is (I assume PHP).

You say your map updates once every 24 ticks...if this is the case, then build your map as an actually image (jpg) and store it for 24 hours. No loading/reloading of arrays, you just grab the picture.

Most PHP solutions come with a gd library that allows you to use the same logic as you mentioned above to "draw" to an image file.

Now, if you have to update the map every 5 to 10 seconds you have another issue.

I've never tried this, but it always seemed like a reasonable solution to me:
Assuming that most map action takes place in a specific area of your map.
Segment your map/arrays into 4 ...keep track of which quadrant you need to re-draw and just re-draw that segment.

         0 0 0 0 0 0 1 0 0 0 0 0 0
         0 0 0 0 0 0 1 0 0 0 0 0 0
A ---> 0 0 0 0 0 0 1 0 0 0 0 0 0   <--- B
         0 0 0 0 0 0 1 0 0 0 0 0 0
         1 1 1 1 1 1 1 1 1 1 1 1 1
         0 0 0 0 0 0 1 0 0 0 0 0 0
C --->0 0 0 0 0 0 1 0 0 0 0 0 0   <--- D
         0 0 0 0 0 0 1 0 0 0 0 0 0
         0 0 0 0 0 0 1 0 0 0 0 0 0

You can continue this philosophy until you get to an optimal map size.


I hope that makes sense.