-
jeudi 10 mars 2011 à 14:49:49
7DRL 2011: Reflections on maps structure
I had an epiphany three days ago, and I could not stop thinking about it since. I realized that dungeon was nothing more than a graph. It does seem to say anything like that, but there are a lot of implications.
This is not a new idea. Others have already spoken before me. For example, Steve Segreto (based on an original work of David Adam) assumes that each cell is a node. A cell in the middle of a room is connected to 8 other cells. This representation gives a lot of nodes and edges. I personally find that it gives too much.
Two reasons make me say this. The first is that algorithms who need to travel many times the graph will have their execution time too long to be reasonable. Do not forget that the maps should not put an eternity to generate. The second reason is that we lose information about the structure of the dungeon itself. We lose the concept of rooms/tunnels. But I find her particularly interesting.
Let's take the example of a monster that is somewhere in the dungeon and tried to reach the player. To do this, consider the Dijkstra pathfinding algorithm. It needs to traverse the entire graph to find a solution. As a result, the execution time can quickly become substantial if the graph is immense. Moreover, once in a room, go to the next tunnel, the shortest route proves to be a straight line (with Bresenham example). Dijkstra's no need to know that. It's the same for tunnels. Once in, there is no real surprise to get to the other side. This representation does not take that into account and we will have to run Dijkstra every time the monster will move one cell. We quickly realize how this representation is expensive. And here it is assumed that there is only one monster that follows the player. Imagine with several…
The way I see a dungeon addresses these issues. Rather than from the fact that cells are the nodes of the graph, I consider that the rooms themselves are the nodes and tunnels are edges. This implies several things. First, the graph is greatly simplified. It has indeed many fewer nodes and a lot less edge. Dijkstra will therefore act to a higher level of abstraction and go faster. He does not calculate the path himself inside a room when he wants to go from one edge to another. Just use a simplified version of Bresenham who give us only the next cell where to go (without having to place the algorithm in full). It's the same for tunnels.
It should be noted that unlike the first representation, the one I propose implies that the cost of the edges is not the same whatever the edge. Indeed, the tunnels do not have the same length and the rooms do not have the same size. We must take this into account during the exploration of the graph. We can already count the number of cells in a tunnel to find the cost of an edge. But it does not include the size of the room. I have not yet found a miraculous solution, but the fairest is to consider a tunnel from the middle of a room to go to the middle of another room. It should therefore, in addition to the number of cells in the tunnel itself, add the number of cells needed to reach the middle of each room that the tunnel connects.
We must also pay attention to the case of tunnels that have branches. Such tunnels will not link only two rooms, but a variable number. One solution might be to avoid such tunnels or consider branching points as pseudo-rooms of size 1 × 1.
Whichever representation is chosen, it is pleasing to note that this allows us to do certain things made totally impossible if we just see a dungeon as a 2D matrix. For instance we can manage to put the maximum distance between the player and the exit (to prevent him from having to finish the level seen just a single room). But it can also be used to generate the dungeon. We construct a graph, and there is actually a dungeon in creating the 2D matrix represents. Although for this example, the second representation is more appropriate.
Well… I have yet push the thinking at the end, but I do see advantages to represent the dungeons as graphs where rooms are nodes and tunnels are edges.
-
jeudi 10 mars 2011 à 13:46:33
7DRL 2011: Anauroch Step 7-9
The three past days have not been very productive. In fact, I spent a lot of time thinking about an idea I had, rather than coding (an idea that gave rise to another post). But this does not mean that I have not advanced.
I could work on the step 7 which is about create a basic combat system. We can fight against monsters. Once they have no more hit points, they disappear. But the player can not die yet. His life points go in the negative. It's just an ease of development to test the game more easily.
For the step 8, I created data files for monsters. In addition to outsource hardcoded data, it allowed me to easily add a new type of monster. I will just have to create more (because two is not really enough). I also took the opportunity to create a class that manages the dice. So the damage a monster can do is not anymore a constant value but a dice like 1d4+1. It's the same for its hit points. All this helps strengthen the randomness of the game, and brings some consistency that strengthens the whole.
Currently I am trying to take care of the step 9. I started by placing (false) items on the map and allow the player to pick them up. I then managed to display the inventory. I'm rather pleased with myself on this one, because with very few lines, I have a very acceptable result. ncurses really deserves that I'm interested more in it. For example, I could create another window in addition to the main, display it above the base window, then close the new window and return to the one below without having to completely redraw myself, as does X. And it's very nice.
As can be seen in the screenshots below, in addition to the display of the inventory, I also managed that the player can throw items. I took care to use a color code for both displays, which although identical, have very different uses.
The next step is to create real items and to use them, equip them, etc.
-
lundi 7 mars 2011 à 14:52:41
7DRL 2011: Anauroch Step 4-6
I have hardcoded a simple map with tuple of string (one string per line). I literally display this structure on the screen (in fact each entry in the tuple is a line on the screen). Collisions are a piece of cake because I juste have to test the content of map[y][x] (a '#' for wall, and '.' for floor). But in python a string is an immutable object. So when I have added some doors, I could not simply make them open in the current structure. So I had to change the map structure. It's now a list of list of Cell (it is a class containing a type like wall, floor or door).
In the fifth step, we should add save/load feature. But I don't want to implement it yet because I think it goes against the principle of permadeath. Maybe I will change my mind later, but meanwhile I will just put this step aside.
The sixth step is about monsters. Just after the map creation, I instantiate some monsters and I put them randomly on the floor. For now they can only move randomly on empty floor cells (so it is impossible for monsters to be on the same cell at the same time).
So for now, I have an hardcoded map with monsters and doors. Monsters can move and we can open doors. The next step will be about monsters AI (to chase the player) and combat system.
-
dimanche 6 mars 2011 à 16:44:02
7DRL 2011: Anauroch Step 1-3
I have just finished the step 3 of the How to Write a Roguelike in 15 Steps guide.
First I have started with the Python HOWTO Curses Programming with Python and the API documentation. I have already done some basic testing with ncurses but never did a full application. Although the HOWTO is not complete, it is enough to start.
Then I've made a title screen. As you can see on the screenshot, I have used toilet with the font letter to render the game name. It's pretty simple but it's doing the job.
Last I've added a yellow @ which is movable with the keypad or directional buttons. For now it's like a snail because he leaves a trail of slime behind him. We can move him in the height directions like any other roguelike.
I am very pleased to have completed this step so quickly. I do not doubt my abilities, but I thought it would take more time because of my learning of ncurses. Well… But there is not something to brag about. I still have a long way to go before it can claim to be a roguelike.
-
dimanche 6 mars 2011 à 12:03:39
7DRL 2011: Anauroch
I have decided to participate to 7DRL Contest 2011. The 7DRL Challenge is an event where everyone is challenged to create a roguelike in a one-week span.
It will be the first time I write a roguelike. I am not new to this game type, but I have never tried to write one. I think it will be very interesting especially because I will start from nothing. I just have emacs and python. I will try to follow the How to Write a Roguelike in 15 Steps guide as much as I can.
I already found a name for the game (I can't write code for a project without a name): "Anauroch". I still have to write it.
I am starting right now (Sunday, 11h00 UTC). Good luck to other participants (and don't forget to sleep).
