• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

This topic is now archived and is closed to further replies.

Feyr

An approach to tile based engine

7 posts in this topic

Is it summarizing too much to say that you're using a sparse matrix setup for the map?

It sounds to me that the "base terrain" (or whatever) would still be a simply 2-dimensional array, and then you're using a sparse matrix to hold the rest of the information.

That about right?

------------------
DavidRM
Samu Games

0

Share this post


Link to post
Share on other sites
This sounds sort of similiar the method I am trying..

I wanted all my objects to be tile independant so I have decided to try storing them in their xyz coords. They will be in a linked list that is depth sorted.

The ground-plane is made up of rectangles that are blitted left to right top to bottom, no fancy diamond shaped stuff; the artwork takes care of that.

I thought I would do this since it speeds up the drawing of the ground plane, and lets me have more time to zsort the objects.

I then iterate through the object list, clipping out the non-viewable objects, sort the list, and draw from back to front..

and I think this should work!

0

Share this post


Link to post
Share on other sites
I don't think this is a too good approach (when you this approach for all Z values) to the problem, because you waste memory when the map doesn't have many blank tiles. For example the ground layer would become very large in linked lists.
This approach, is also a bit slow, because finding a value in a large list is not fast. When you use these lists with larger X, Y values and you search for a region these lists slow you down.
Example :

RECT DisplayRect;

for ( int z = 0; z < maxZ; ++z )
{
ptr = [Z(z)] // search for Z Values -> fast
Search( ptr, DisplayRect.top, SearchResultY )
for ( y = SearchResultY; y < DisplayRect.right; .. )
{
Search( y, DisplayRect.left, SearchResultX );
for ( x = SearchResultX; x < DisplayRect.right )
{
// Draw etc.
}
}
}

When now the Width and Heigth of the Map are large, the time critical parts ( Search(..) ) become very slow (using indexing could be a slight relief).
For small maps or maps with many blank fields this technique could become fast and efficent.

I suggest (as an OOP addict) using for each height different Map implementations.
e.g.

class CMapBase
{
virtual void Draw( CRect& area, LPDDSURFACE ) = 0;
// etc.
};

Then
class CGroundMap : pubic CMapBase
{
virtual void Draw( CRect& area, LPDDSURFACE );
private:
matrix m_Map;
};

If you keep this implementation clear, straightforward and easy to (use/edit) you can get very good results.
An implementation for the heighest Z value can be somewhat to reduce calculating costs, by using your method, because only few Tiles will be so high up, so that a matrix would be too large.

Hope made myself clear ?

Aidan

PS : Email CKoschack@T-Online.de if you have suggestions, comments

0

Share this post


Link to post
Share on other sites
I use a 2D array for the base map (square tiles, but I figure you know that by now ), but keep everything else in a large array.

For rendering, I create a tree (sorted in screen depth, for back-to-front rendering) of the visible items in the array - no malloc here, I simply create the tree within the array, giving me the best of both worlds (with a certain waste of memory, yes!). When things change, I re-sort the active visible items in the array (and only those).

I was initially worried that this would suck from a performance perspective, but as it turns out, it doesn't. Even with several hundred active items, sorting and recursing is less than 1% of the time spend in rendering.

This approach has at least one major benefit: There are really no firmly defined "layers", each item is free to move in (x,y,z) space as I see fit. Also, memory is directly proportional to "map density".

/Niels

0

Share this post


Link to post
Share on other sites
I am too using a method such as that described above (and as T-man said). My method does the following:
You have a base array (2D). Each element in the array is the head node to a linked list. Each linked list is a list of objects (sorted by Z order) over a given 2D point. When an object moves, resorting is done only over that 2D space. (NOTE: An object can be anything from a basic non-interactive tile to an interactive entity).

Now there is another list that needs to be mentioned here. In my design, I had a problem when drawing the images. The method above is great for storing it in memory, but when drawing the objects, it failed big time. Here's the solution I came up with. I have a linked list of objects that would be drawn sorted by their pixel position. These objects are only the currently visible ones. Each node in the linked list points to an element of the map in memory and has a link to the next and previous node in the list. This allows me to quickly move the object up and down the drawing list whenever an object moves.

I will be writing up an article on this method and post it up on my page for the standard critism such as:
"That will never work you stupid stupid man!"
"Go code some business application you loser!"
"You couldn't tell a linked list from an array!"
and so forth

I'll let you know when it's up.

------------------
Dino M. Gambone
http://www.xyphus.com/users/dino

Good judgement is gained through experience. Experience, however, is gained through bad judgement.


0

Share this post


Link to post
Share on other sites
I finally finished writting the article on the method described above. Here's the link to the site:
http://www.xyphus.com/users/dino/technical.html

Happy reading!

------------------
Dino M. Gambone
http://www.xyphus.com/users/dino

Good judgement is gained through experience. Experience, however, is gained through bad judgement.


0

Share this post


Link to post
Share on other sites
Hiya all. I was just brainstorming for ideas on how to store and render the map for a tile-based engine. I've read a few docs and written parts of two or three engines myself. Anyway, the point is this. I've come up with an approach that I've never seen done before, and that appears to be an improvement over some techniques I've read about. I'd like to get the opinion of this group of programmers on this implementation, any problems or improvements that you guys can point out and, if possible, material that discusses this particular technique (which I haven't found so far.)

The method for storing a tile map that I've most often seen written about is to create a 3 dimensional array or linked list of tiles, with the X, Y and Z indices of each tile serving to place it on the X, Y and Z axes. When the rendering function is called, each tile is drawn starting with the top left of the screen at the bottom layer, going through to the bottom right of the screen at the top layer, with every tile being in between being drawn (or possibly skipped, if it the programmer tests for blank tiles.) There are a couple problems with this setup, however. The first is storage: it seems wasteful to me to use memory on a tile that is nothing but a placeholder. The second is time: if the tile is blank, and is drawn, then time is wasted testing each pixel for transparency (the time is less if the images are RLE, of course.) And if the tile is blank and the renderer skips to the next tile, then every tile that is placed or skipped is accompanied by a corresponding test to see if the tile is empty. Those tests don't matter much individually, but with high resolutions or many layers they are likely to slow the render down. Below are a few modifications to the storage scheme and rendering function that I think will help ease these problems.

A linked list (the map) of linked lists (the rows) of tiles (the individual tiles) is created. Each row list contains the index of the list (from 0 through MapHeight-1), and the rows are initially empty. As the map data is read from the disk, new nodes are added to whatever row they belong to. Each node contains its X index (from 0 through MapWidth-1)...but empty tiles are skipped. For instance, take a look at this 3x3x1 map, and the accompanying representation of the linked list that would be built from it (it looks better in proportional font =/ ):

- = blank tile
* = non-blank tile
0 1 2
0 * - *
1 - - -
2 - * -

[Z 0]
|
[Y 0]->[X 0]->[X 2]
|
[Y 1]
|
[Y 2]->[X 1]

In each node labeled X # the tile image would be stored. When the render loop begins, it would search through the Z0 linked list for the lowest number that is greater than the Y coordinate of the screen (we'll assume the screen is at location 0,0 with a size of 3x3 tiles.) It would come to the Y0 list, and search for the lowest number that is greater than the X coordinate of the screen, which would be X0. It would then walk down the list, drawing each tile as it comes to it, until it reaches the end of the list or the end of the screen (both of which are X2 in this case.) It would then continue with the list Y1 (where it would reach the end of the list as soon as it started, and so would continue to Y2.) Hopefully this explanation has been clear enough for you to see that in this instance there are many less blits required (3) than would be performed if the tiles were stored in an array or solidly filled linked list (9).

Okay, like I've mentioned, I would appreciate any comments, improvements or criticisms of this map storage technique. Here are a few possible problems:

First, calculating the X offset for each tile is less straightforward than in a solid array. The X index would have to be multiplied by the tile width each time a new tile is drawn instead of simply adding the tile width to the X offset. I don't know whether replacing a test to see if the tile should be skipped with a multiplication would save or lose time.

Second, for very dense layers, the map data plus pointers is likely to exceed the memory required for a solid array of map data.

Thanks for your time =)

--Feyr

[This message has been edited by Feyr (edited October 20, 1999).]

0

Share this post


Link to post
Share on other sites