View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Looking for a code/desgin review of continous map implemention

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

15 replies to this topic

#1Valgor  Members

Posted 28 October 2012 - 07:22 PM

Hello, incoming huge post! I am creating a 2D RPG where the entire world is open and continous. That is, there are no instances (for now). I am looking for any and all criticism over my design and code. I also hope this will help future developers. I will explain my ideas and walk through the design. At the bottom you can find my entire implemention.

The world is divided up into tiles where each tile is one image. Each tile is named "X_Y" where x and y are the coordinates with respect to the entire world. Suppose our playable character starts in 3_3, and the tile the character is actively in is called the center tile. The character renders to the center of the screen always (think Diablo), so we keep track of the map tile's (x,y) position and also the character's (x,y) position relative to the map. The difference in distance between the two is called the xOffSet and yOffSet.

There are two main steps in the Update method. (1) Checks to see if we need to load nearby tile and (2) see if we are no longer in the center tile.

(1) The center tile has an interboundry rectangle, so that if this boundary is crossed, we must load a nearby tile to render. Suppose we are in 3_3 moving east towards the edge so the 4_3 must be loaded. The code to check for this is here:

[source lang="csharp"]if (Math.Abs(mapPosition.X) > interBoundaryWidth){ if (!bEast) { Load(EAST, 1, 0); bEast = true; }}else if (bEast){ Unload(EAST); bEast = false;}[/source]

Similar sections of code are used for all possible directions including the need to load NE, NW, SE, and SW maps.

(2) This section sees if our character has moved out of the center tile and into another. Continuing with the east example, suppose our character moves from being in 3_3 into 4_3.

[source lang="csharp"]if (Math.Abs(mapPosition.X) + (GraphicsDeviceManager.DefaultBackBufferWidth / 2) > tileWidth){ foreach (MapTile bt in mapTiles) { if (bt.direction == CENTER) bt.direction = WEST; else if (bt.direction == NORTH) bt.direction = NW; else if (bt.direction == SOUTH) bt.direction = SW; } foreach (MapTile bt in mapTiles) { if (bt.direction == EAST) { bt.direction = CENTER; mapName = bt.name; } else if (bt.direction == NE) bt.direction = NORTH; else if (bt.direction == SE) bt.direction = SOUTH; }worldManager.setCharacterPosition(new Vector2(characterPosition.X + tileWidth, characterPosition.Y));[/source]

The first if statement sees if we have crossed outside of the map tile's width and thus into a new map tile. If we have, we want to update all the tiles to reflect the direction on the new center tile. Consider this crude drawing that maps each possible tile into the new direction. Note that only the N/NE or S/SE sections could possibly be loaded at the same time since the north and south tiles cannot be loaded at the same time because the maps are bigger than our screen. "C" is for "Center" which is where our character is located.

--------- -----------
| N | NE | | NW | N |
---------- ------------
| C | E | ---> | W | C |
---------- ------------
|S | SE | | SW | S |
---------- ------------

So our center tile becomes the west tile, and the west tile becomes the center tile, and so on for the other tiles. The order of changing the directions is important, which is why I have two foreach loops. Lastly, we update the character's position to that it starts on the far left side of the new center tile.

Finally, the rendering is based on the tile's direction which can be seen in my code below. If you have read this far, please leave a comment! I'm open to improvements and hopefully would like to help others tackling this problem. Thanks for reading!

#2Valgor  Members

Posted 28 October 2012 - 07:26 PM

For some reason there are no spaces between the boxes! It is a matrix transformed into another matrix. Written out:

[ N, NE, C, E, S, SE] ---> [ NW, N, W, C, SW, S]

Match this with what I have in the above post. Hope that makes sense.

#3phil_t  Members

Posted 28 October 2012 - 10:08 PM

I'm not sure I understand the need for all the code about directions (but maybe I'm missing something).

Seems like on each update cycle you could just figure out which tiles need to be loaded based on the player's current position in the map, and the size of the screen. Then compare that to a list of currently loaded tiles, and unload and load as necessary.

#4Valgor  Members

Posted 29 October 2012 - 08:47 AM

I'm not sure I understand the need for all the code about directions ... you could just figure out which tiles need to be loaded based on the player's current position in the map

Figuring out which tile to load is what the direction code is about. It's a book keeping system to see which one to load based on your current tile and also helps to let the program know where to render that tile on the screen.

#5Gophur  Members

Posted 29 October 2012 - 09:34 AM

I'm not a coder so I have no real idea if this will be helpful BUT...

I have worked on the largest MMo map in history for about 10 years and the biggest head ache we've had was workign with world origin offsets. The problem is that our world size and need for placement precision of active and passive entities meant we had to use relative locations.

Why exactly is this an issue? I'm not the tech guy I just produce but I can tell you it is worth thinking about given the sheer amount of complaining about the system that my guys have given me over the years.

Hope it's woth a penny.

#6Gophur  Members

Posted 29 October 2012 - 09:36 AM

I'm not sure I understand the need for all the code about directions ... you could just figure out which tiles need to be loaded based on the player's current position in the map

Figuring out which tile to load is what the direction code is about. It's a book keeping system to see which one to load based on your current tile and also helps to let the program know where to render that tile on the screen.

I assume you're loading tiles in the direction the player is moving? We tried that early on (long time ago so may be better now) but it was easier just to assume that in our world a player could move to any of the 8 surrounding tiles and that any of them could be drawn at any time so load all of them and to reduce any load stutters to thread the loading of the next 16 edge tiles as well.

#7phil_t  Members

Posted 29 October 2012 - 11:12 AM

I'm not sure I understand the need for all the code about directions ... you could just figure out which tiles need to be loaded based on the player's current position in the map

Figuring out which tile to load is what the direction code is about. It's a book keeping system to see which one to load based on your current tile and also helps to let the program know where to render that tile on the screen.

I guess I'm just not sure why the direction the player is moving is important. This is an open world game, so why are the tiles in the direction he is facing more important than those behind him? All that should matter is the player's position and the "radius" around him that you want loaded (which also would simplify the code a lot).

#8Telcontar  Members

Posted 29 October 2012 - 01:53 PM

I believe (though I'm not sure) that Gopher is referring to keeping a buffer of pre-loaded tiles around your character so they never have to wait for the game to load an area.

Depending on how fast your load/unload code is (which will depend on how much information is contained within each game location, among other things) there could be a non-negligible time from the load call to when the area is actually available in memory. Thus, you want to actually start loading the area a safe amount of time before the player would see it. Gopher seems to be implying a predictive model based on travel direction.

In a current design project, I'm toying with another solution; basically it boils down to loading a larger area. Instead of loading only the immediate surrounding area and possibly having to reload every time the player crosses a certain boundary (imagine a player moving back and forth across that domain boundary, incurring tile loads each time) I add another buffer.

Loaded area (try to imagine it as a square):
XXXXX
X___X
X_P_X
X___X
XXXXX

At any given time the game has a 5x5 supertile area loaded into memory. The player's view is substantially smaller than this. The Player (P) can move to any of the tiles denoted by underscores (within the X boundary, also loaded in memory) without incurring a subsequent load of any new space. When he does move into an X boundary, the loaded area moves so that the X tile moved into becomes the center of the new area - thus the player can return in the direction he came for a ways without the game needing to load again.

Of course, this basically trades larger load volume for lower load frequency, so it may not be optimal for all games and situations. If loading is fast enough, it might not be that big of a deal to just do a lot of it.

I Create Games to Help Tell Stories

#9slayemin  Members

Posted 30 October 2012 - 09:35 AM

Hold on, I'm not quite sure I understand how you're describing your maps...

Is it a tile based system, where you have a 100x100 grid of tiles, all rendered on the screen at once?
Or is it a system where each map grid is an area which fills up the entire screen (like old school Zelda) and you move in the cardinal directions to go to the next area?

#10ultramailman  Prime Members

Posted 30 October 2012 - 01:26 PM

Hello Valgor

I am working on the same thing as you, except I call my "tiles" "cells" instead, because the word "tile" is reserved for little blue and brown bricks that make up the world. What I do is I keep a 3x3 2d array. array[1][1] is the center cell, and the others are the neighbor cells. Every time the player changes to a new cell, all the surrounding 8 cells are loaded too.

Each character has a position that is in pixel units, and each cell has a position that is in cell units. To calculate which cell a character should be in, I do this:
cell_x = character.pos.x / CELL_WIDTH
cell_y = character.pos.y / CELL_HEIGHT


#11Valgor  Members

Posted 31 October 2012 - 06:05 AM

Hold on, I'm not quite sure I understand how you're describing your maps...

Is it a tile based system, where you have a 100x100 grid of tiles, all rendered on the screen at once?
Or is it a system where each map grid is an area which fills up the entire screen (like old school Zelda) and you move in the cardinal directions to go to the next area?

Not like Zelda. The world is, say, a 100x100 grid of tiles. If you are in tile, say, 5_5 and within a boundry inside of that tile, then that is the only tile loaded. If you pass that inter boundry then neigboring tile are then loaded. Only a maximum of four tiles will ever be loaded. So if you are in 5_5 and move the northeast corner of that tile, then the following maps get loaded: 6_5 (east tile), 5_4 (north tile), and 6_4 (NE tile), and 5_5 is still loaded. Once you move into another tile and move within it's inter boundry, you can unload the older tiles, leaving only the current tile you are in in memory.

#12Valgor  Members

Posted 31 October 2012 - 06:10 AM

Hello Valgor

I am working on the same thing as you, except I call my "tiles" "cells" instead, because the word "tile" is reserved for little blue and brown bricks that make up the world. What I do is I keep a 3x3 2d array. array[1][1] is the center cell, and the others are the neighbor cells. Every time the player changes to a new cell, all the surrounding 8 cells are loaded too.

Using the word "cell" does sound like a better idea! I started out with the idea you have, using the surrounding 8 cells, but I thought there would be too much over head updating and moving content around the data structure that holds the current world (in your case, an array). So if you move to the east, then you have to load three new cells and move 6 cells in your arrays. I wanted to smiplfy this, so I am assuming I will be using larger maps and will only need to update at max 4 cells ever.

#13slayemin  Members

Posted 31 October 2012 - 12:19 PM

Okay, I think I understand.

I didn't see this mentioned in your post or in your code, so I'll bring it up. If the player is on the edge of the map, how do you handle it? If you have a grid of 100x100 tiles, the view is always centered on the player, and the player is located at (0,0) (top left corner), what happens? Do you keep the player centered or does the player move to the top left corner of the screen?

(x).ToString() + "_" + (y).ToString();
You don't need to surround your variables with parentheses.

I think your whole approach is flawed, and I'm not saying that to be mean. Here is what I'd change:
1. Use a camera.
2. Store your tiles in a 2D array.
3. Use a quad tree for collision detection.
4. Use "layers" in your map (terrain, static terrain objects, creatures & items, etc).
5. Break your map class up into more objects.

Use a camera:
What you want to do is to create a camera viewing rectangle. If map objects are within the viewing rectangle of the camera, then they are rendered. If you treat your view as a viewing rectangle, you can do a lot more with it (panning, zooming in and out, centering on an object, tweening between points, etc). Rather than rendering everything relative to the character position, you render everything relative to the center position of the camera and, for the most part, keep the camera centered on the player. This makes it much easier to handle the map-edge cases. You could also do interesting features, where if your character is moving in a particular direction very quickly, you can adjust the veiwing area of the camera to show more of the world space in front of the character so that they have more time to react.

Store your tiles in a 2D array:
You can either store the tile objects directly, or just store an index in a 2D array. How you store your tiles should be independent of how you're moving on the tiles and viewing the tiles. Your character movement can be simplified into an X & Y position, and handled with requests to the map manager. Character tells the map "I am at this position. I want to move left one space", and the map manager reads the map array and says "Okay, that's a legal move! you can set your position there." or "Nope, that can't be done. There's a tree there!" or "Nope, you're on the edge of the map and you can't go left any further!"

Use a quad tree for collision detection:
Once I understood the concept, it didn't take me more than an hour or two to get a quad tree datastructure up and running. The idea is to put your spatial objects into the smallest box which will contain them, and keep dividing the box into fourths until its empty. Then, when you're doing collision detection, you only need to compare the objects in the largest box against all of its child cells. This changes your collision checks from O(N*N) to O(log N) (best case). The tiles which are being viewed would be all the tiles which collide with the camera viewing rectangle (don't necessarily need a quad tree for camera rect, you can also do a rect.Contains() call against all tiles in the game model which is more computationally expensive but works)

Use layers in your map:
Terrain is the first, bottom layer. This tends to make for boring maps because they're plain. So, create another layer and add trees, flowers, rocks, and any other terrain objects. These static terrain objects are non-moving, so this simplifies collision detection a bit (you're not checking if a tree is colliding with another tree every frame). Then, you'll also have another layer for moving objects (monsters, player characters, bullets, pick ups, etc). These objects may move every frame, so they can collide with other objects in their layer or objects in the static objects layer. By layering your map, you can be a bit more flexible. A tree can sit on a dirt tile or a grass tile, instead of creating a tree-dirt tile and tree-grass tile.

Break your map class up into more objects:
Some people like to break it out even further and add a data layer to handle data read/writes to and from a file or database. I generally include that in my game model objects.
So, I'd create at least the following classes:
-Map
-Tile
-Character
-Camera
-Player (inherits from character)
-Monster (inherits from character)
The map class would contain one or more 2D arrays of tiles, any meta data about the map (like map name, map size, etc), and methods for loading and saving to disk.
A tile class would contain tile specific information, such as the tile texture, tile dimensions, tile type, movement point costs, etc.
The character class would be an abstract game actor class which contains generic data about a character (hitpoints, name, position, dimensions, etc)
A player class would mostly have UI and controller specific methods
The monster class would be an extension of the character class, maybe with some added AI scripts to control it and do monster specific logic.
I like to keep a global class of loaded art resources (and call it a texture database, or TextureDB for short). Whenever I create a new object, I set its texture to point to one of those stored art assets. By doing this, I can centralize all of my resource loading into one object. Then, all I have to worry about is making sure that the TextureDB has all of the correct art assets loaded up. I can also load art assets into the TextureDB by reading a file for a list of needed art resources (art manifest), so if I load a game level, the level data would contain a list of all the art resources it uses. The textureDB would load those assets into memory, and off we go!

Warning: general hand waving to follow:

As for your rendering code, all you should be doing in the draw function is calling each object and telling it to render itself according to its current state. So, if you have a map object, your render code should be this:
Map.draw(spriteBatch);

Since the map contains a list of tiles which will know how to render themselves, it'll do the following:
//you'd also do a foreach for each layer, so you render terrain first, followed by static objects layer from top to bottom, followed by moving objects layer, etc.
foreach(Tile t in TileList)
{
t.draw(spriteBatch, position);
}


To move a character on a map, you'd make a request call to the map manager, something like this:
if(KeyboardInput == MoveLeft)
MyCharacter.Position = Map.MoveTo(MyCharacter.Position, new Vector2(-1,0));


And the map manager would get the request and handle it something like this:
public Vector2 MoveTo(Vector2 Pos, Vector2 Dir)
{
Vector2 RequestedTile = new Vector2(Pos.X + Dir.X, Pos.Y + Dir.Y);

if(Tile[RequestedTile.X][RequestedTile.Y].isPassable() and not Tile[RequestedTile.X][RequestedTile.Y].isOccupied() and blah blah blah conditions)
{
return new Vector(RequestedTile);
}
else
{
return Pos;
}
}


#14Valgor  Members

Posted 31 October 2012 - 04:52 PM

Thank you so much for taking the time to respond in so much detail! There is much to think on.

A player will never reach the edge of the world ( tile 0_0 at position 0,0) because the world will be one large island, or blocked by impassable mountains.

Using a camera rectrangle - I like this idea. I've thought about it before but figure that might be something to mess with later. QuadTree research and implemention was next in line after getting a continous map working.

When you say to store the tiles in a 2d array and/or have a TextureDB class, I just want to be clear you aren't suggesting we load all maps and textures into the memory? I'm loading maps from the harddrive as they are needed. I would toy with the idea of a buffer, but if the entire map is huge?

Thank you for the break down of my class and suggestions to the over all design!

#15ultramailman  Prime Members

Posted 31 October 2012 - 08:04 PM

When you say to store the tiles in a 2d array and/or have a TextureDB class, I just want to be clear you aren't suggesting we load all maps and textures into the memory? I'm loading maps from the harddrive as they are needed. I would toy with the idea of a buffer, but if the entire map is huge?

I think tile is the word commonly used for the blocks that make up the terrain, be it a rock, wall, tree, etc. So most likely slayermin refers to the blocks, not the room/cell that contains your player and the blocks.

but I thought there would be too much over head updating and moving content around the data structure that holds the current world

each cell ( I'll continue to call them cells, to keep my posts consistent) keeps track of a rectangle (x, y, w, h). The rectangle's x and y will be the position of the cell's upper left corner. w and h will be the cell's width and height. This rectangle represents the cell's area.

Another rectangle, I call it the area_of_load, will have a smaller area than a cell's rectangle.
Every frame, this area_of_load rectangle will be updated to have the same center as the player's center.
Next, check if the cell's area rectangle contains the area_of_load. If it does, no loading of adjacent cells is required. If it doesn't, then figure out which cell needs to be loaded, and load it.

Thats my initial approach, but I went with load all surrounding cells in the end for simplicity. Tell me what you think of this ;o

#16slayemin  Members

Posted 01 November 2012 - 05:02 AM

When you say to store the tiles in a 2d array and/or have a TextureDB class, I just want to be clear you aren't suggesting we load all maps and textures into the memory? I'm loading maps from the harddrive as they are needed. I would toy with the idea of a buffer, but if the entire map is huge?

I think tile is the word commonly used for the blocks that make up the terrain, be it a rock, wall, tree, etc. So most likely slayermin refers to the blocks, not the room/cell that contains your player and the blocks.

Yes, this is right.

Initially, store each tile block texture in memory. If you're concerned about memory usage, you can store a list of the assets you need in a file manifest which is added to a level file. But, parsing that is extra work and may be totally unnecessary if your textures don't consume much memory (computers come with gigs of ram these days). I tend to wait until it becomes a problem before I start trying to solve it. It may not be the most efficient with computer resources, but it is the most efficient with my time.

Let the map in memory be an array of integers, where each integer corresponds to a map tile ID, and the array indices are the X & Y coordinates.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.