How to Generate a Map in Java?

Question

I trying to complete a RPG game for a project, but have no idea on how to make the game map. It doesn't need to be graphical, but the code for the whole map and each tile must be correct.

So far, I thought about making a non-matricial map (as request by the professor) by using an ArrayList which contain all the linked tiles.

public abstract class Casella {
/** 
 * @uml.property name="tabellone"
 * @uml.associationEnd multiplicity="(1 1)" inverse="casella:Tabellone"
 * @uml.association name="contains"
 */

private int id;
private boolean free = true;
private List adjacent;
private List items;
private Tabellone tabellone = null;

public void in(){
 free = false;
}

public void out(){
 free = true;
}

}

This was the code for a single tile (which has 3 classes that extends it). I still have no idea on how to put together and generate a map.

Thank you for your time.

Answer 1

Don't start with the implementation, start with how you would like to use the map. That will give you some constraints how to implement it. For example:

When drawing the map, how do you access it? By coordinate? Or by "go west from tile X"?

[EDIT] I suggest to start with the main loop of the RPG game. You'll need to place the character/token somewhere (i.e. it needs some kind of relation to a tile).

Then you need to move the character. A character must be able to examine the current tile (opponents, items, type). It needs a way to know how it can move (i.e. is there a wall to the right?)

This gives you an interface for your map: Services which it renders for other objects in the game. When you have an idea of what the interface needs to provide, that should give you an idea how to implement the map (the data structure).

As for generating a map, use a random number generator plus some "common sense". Have a look at the adjacent tiles: When they are all city, this tile is probably city, too. Same for plains. Hills are singular items, and they are least frequent.

Run this code, print the map as ASCII ("C"ity, "P"lain, "H"ill) to see if it works.

Answer 2

If it's a tile-based map, then each room has a fixed relationship with its adjacent rooms. You may not need to worry about co-ordinates (although it might be simpler if the tiles are square), but you will need to worry about directions.

If the tiles are square, cardinal directions (n, s, e, w) may be all you need care about. If they're hex tiles, you can number your exits 1-6 (perhaps with static final constants). Then each adjacent tile may be linked to this one along with its exit.

Answer 3

As said by Aaron, you need to decide first how the maping coordinates will be.

But you are not constrained by an X-Y-Z coordinate system. For instance, each tile could be linked to any other tile on your map. It all depends on how you want to build it.

You say that you're building an RPG game, then you need to have a good view of the terrain surround your character. Is it multi-level? How does the character move from one tile to another? Is the movement one way?

There are, literally, dozens of question to be asked when designing a map for a game.

You need to plan it very well first, before starting coding.

Answer 4

Is speed or memory a huge concern for this project? If not, why don't you use a 2d array?

Something like

Casella map [][] = new Casella[xSize][ySize];

From here it is easy to conceptualize, just picture it as an excel spreadsheet where each cell is a tile on the map.

The way you are going is fine though, just a little hard to conceptualize sometimes. You have a List of adjacent tiles. So, when creating your map you start somewhere, possibly top left, and go from there.

You could use nested for loops in order to set up the map, and to help determine the edge items.

for(int i = 0; i < XSIZE ; ++i)
    for(int j = 0; j < YSIZE ; ++j)
        if(j==0) //found left edge (i.e. no adjacent ones to the left)
        if(j==(YSIZE)) //found right edge (you get the picture)

The point of using the loops, and checking the edges, is that you are going to need to link backwards and forward, up and down for each tile except at the edges, where you will have either 2 or 3 links instead of 4.

Answer 5

To generate a map like this without using a matrix, I recommend starting with a center tile and then populating the map outwards by using a modified breadth first search algorithm. First of all, we'll need something a little better than a list of adjacent tiles. You could simply have four variables, one for each direction that stores the next tile, as such:

private Tabellone up = null;
private Tabellone down = null;
private Tabellone left = null;
private Tabellone right = null;

Say we start with the center-most tile. All you have to do now is figure out how many of the directions are null, and create a new Tablellone object for each direction, making sure to set each of the variables in this current object and to set the appropriate opposite variable in the object created.

Tabellone adj = new Tabellone();
up = adj;
adj.setDown(this);

Once you've filled out all of the directions on this tile, you then choose one of the other tiles you've created and perform the same operation. This is where the breadth-first search algorithm comes in. You can use a queue to go through each tile you've created and fill out the directions. To make the algorithm stop, simply set a limit on the number of tiles you want to create and use a counter to keep track of how many have been created.

int count = 0;
ArrayList<Tabellone> queue = new ArrayList<Tabellone>()
queue.add(/*center tile*/);
while (count < 100) { //if we want 100 tiles
  //take out the center tile from the beginning of the array list, create a tile for each direction and add those tiles to the array list, then increment count by 1.
}

Note: This algorithm as it stands will create a diamond shaped map, if you want a square, you'd need to have a variable for each diagonal direction as well.

Of course, if this seems a little more complicated than you'd like, I'd recommend a coordinate system.

Answer 6

The code needs to be correct really isn't a functional requirement, so its hard to say exactly what is correct without knowing more about your game/map.

Assuming you have a map that has X tiles and no ordered adjacency a non-matricial solution is best, a common solution is to just model it like a graph using either adjacency list for non-symmetric adjacency or incidence list for symmetric adjacency. If youre using an incidence list you need an edge object that contain the vertices the edge is connecting, if youre using adjacency list a multimap might be cool to use.

If you want a non-matricial solution with ordered adjacency AlbertoPL has the solution for that.

Assuming you have a map thats X tiles wide and Y tiles tall and the tiles that are next to each other are adjacent, so that each tile has at max 4 and min 2 adjacent tiles you could use a matrix to access the tiles and also represent adjacency by matricial adjacency. The idea is that map[Y][X] is adjacent to map[Y+1][X] and map[Y][X+1] and reversely. This solution could also fit max 6 and min 3 tile adjacency if tile [Y+1][X+1] is adjacent to tile [Y][X]. Upside to this is that you can easily parse the map, and since it has 2 dimensions its natural to model it like this. Downside is that once a tile is set, you cant change its adjacency without changing the matrix. As this isnt what you professor suggested you might not want to do it, but if you have (static) ordered adjacency this might be easiest way to do it.

Answer 7

I managed this by using adjacency lists. Each cell will have an ArrayList containing the indexes of the adjacent cells. Those indexes are the ones that the said cell have in the map ArrayList of cells.

http://en.wikipedia.org/wiki/Adjacency_list