There are 2 kinds of tiles in the map matrix:
1. not walk-able ,value 1; 2. walk-able, value 0;
The target is make a walk-able rout, value 0 on the map matrix to connect all rooms so that they are all accessible.
Normal way of doing it is calculating the distance between two tiles from two rooms and pick the nearest two to make route from as shown on the image below.
But I used another way to do it.
The thought is very simple: each time, enlarge the room by 1 unit until the room meet other rooms. From the contact unit, find the rout.
To illustrate it:
Expand the edge tiles
As can be seen. The edge units expand by 1, if there's no contacts, the units created by last expand expand again. This process repeats until all routs are found. Then we come across with another problem: when do we know we have all the routs and stop expanding?
numbers of routs
the target is : making all the rooms accessible, this means all rooms are connected into one area.
If we have n rooms, at least n-1 routs should be used to connect them. Can we say, if we have n-1 routs all rooms are connected ? Yes, with one condition : not routs are redundant. But what is a redundant rout? A redundant rout is a rout that connects two rooms which are already connected in other way. Here's an example:
A B C D are four rooms. The line between two rooms stand for a rout.
As can be seen, in the left example, 1 2 3 connect all four rooms, but in the right example, 1 2 4 can not connect four rooms. D is isolated. Because 4 is a redundant rout that connects room C and B which are already connected through 1 2 and A.
To implement this is very simple. When a new rout is created, two rooms which are connected by the rout is marked as connected. Before creating another new rout, check the two rooms that will be connected by the rout. If there is at least one unconnected room, this is not a redundant rout and can be created.
Illustrate this with the right side example: red rooms are connected rooms. When rout 1 is created , A and B are marked, when rout 2 is created, C is marked as well. Before making new rout 4, B and C are checked for connected mark, but as B and C are all marked as connected, so rout 4 is not a valid rout, need to find another room.
get the rout from contact point
There is still one problem need to be solve before I can start with designing the functions:
When we get the contact tile, how to find out other tiles on the rout.
When enlarging the room, a tile get the four neighbor tiles around it. if the neighbor tiles do not belong to the room, they are added to the enlarge list. In other word, each expanded tile has base tiles from where it is created. Thus it is possible to search back all the tiles until we meet the room. The contact tile will have two base tiles.
In the following example, the contact tile where B and C meet is marked with thick outline. The arrows between the tiles shows from which tile the new tile is created. The number on the tiles stand for index of the tile. For room C, tile 0 expand to tile 1, tile 1 expand to tile 3 which is the contact tile. To search back, tile 3 's base tile is tile 2, tile 2's base tile is tile 1, tile 1 's base class is tile 0, tile 0 belong to room C. So the rout connect room C and B on C's side is [tile 1, tile 2, tile 3]
To store this structure, just add two properties to the already existed CoordTile class (The CoordTile class is used to store information for each tiles includes coordinator of the tile, walk-ability of the tile)
CoordTile parent1;
CoordTile parent2;
Use these two properties to store from which tile this tile is enlarged.
Design the functions
1. makeRout : iterate through a list of routs, get each tile from the rout and make the tile 0 (walkable) on the map matrix
2. getRoutList : get route by enlarging all rooms until all routs are found
3. swellRoom : enlarge all the rooms by one unit, if there are any contact point, get the rout from that point
4. getRoutViaTile : from the contact point search back for all the tiles on the rout.
The result
I close the function of deleting small isolated room, as I want more rooms to test.
As can be seen, all the rooms are connected even it only has one tile.
The Code
you can find the source here:
No comments:
Post a Comment