-
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).
-
samedi 11 juillet 2009 à 01:17:05
GSoC & me #2
It's been six weeks since I started the GSoC on Gajim.
For now, I am done with roster versioning. Now I'm going to explain the walkthrough.
The last time, I told you about the tables I'm using. The format of the first table, the one which stores the roster entries, changed a bit. Indeed, before I didn't store the state of the "ask". Here is the final format of the 2 tables:
CREATE TABLE roster_entry ( account_jid_id INTEGER, jid_id INTEGER, name TEXT, subscription INTEGER, ask BOOLEAN, PRIMARY KEY (account_jid_id, jid_id) ); CREATE TABLE roster_group ( account_jid_id INTEGER, jid_id INTEGER, group_name TEXT, PRIMARY KEY (account_jid_id, jid_id, group_name) );WARNING: when we give None to a text field, sqlite will put the text "none". So we have to convert the None in "". Else when we get back the value of the fields, we have "none" strings instead of None.
I'll never thank Matthew Wild enough for Prosody. His software allowed me to test very well my implementation in Gajim. It has been the occasion for him to put his to a severe test. That's like that I found some bugs in Prosody. Bugs that he corrected as fast as he could. Moreover I advise anyone who wants to implement the roster versioning in a client to use prosody as server to do their tests. The server can be easily installed and is very light.
So the roster versioning is now operational in Prosoddy and Gajim. Moreover Asterix just merged my branch with the trunk. The roster versioning is now accessible to anyone that is using the trunk and a server that manages it (i.e only prosody for now).
Please note too that johnny (reachable on the official chatroom of gajim) who did a big sort of gajim's bugs, found an old feature request. It's the report #3190 in which Liorithiel asked that the roster is stored client side. Then when you turn on Gajim we would see our roster without being forced to be online. This is very pratical when the server is down or when we have some unread messages and we don't want to go online for that few. It's also more pratical to search through a contact's logs.
It was not planed at the beginning but since it has been asked very nicely, I did it. So now we can fully benefit it. Because of that, even if your server don't manage the roster versioning, you can still benefit what I have made. Isn't the life wonderful ?
In the previous post Merwok asked me to explain a bit what is the roster versioning. That's true I didn't give enough explanation. I advise the reading of the introduction of the XEP-0237 that explains it very well. Here is a short résumé: instead of receiving the full roster at each connexion, the server only sends the changes since the last connexion. Thereby the connexion is a lot faster all the more when we have a big roster.
Now i have to implement the XEP-0136. It was sold to me as a vulgar way to store chat logs on the server. And yet it's a lot more than that. This XEP allows to define a true policy for the logs management. We can say by example that we always want that our discussions are stored or they are never stored or that we don't care (it's a big résumé). I'll give more details about the mechanism when i'll start the implementation.
From my complicated calculations, we stand a one in twelve chance of not being able to talk with our contact. Indeed when we start a discussion, there is first a negociation. It must determine if we have to record or not the discussions, based on the policy of both sides. In the case where one of both absolutely wants to record the discussion and the other doesn't want at all, the negotiation fails. The XEP is very clear with that: "The negotiation fails and the parties MUST NOT exchange any messages". I must admit that I can't wait to work on this part of the implementation, go and find out why. :D
Server side, I must work with ejabberd and mod_archive_odbc this time. Indeed we can't absolutely rely to the page listing the XEPs managed by ejabberd. It shows that we must use mod_archive which is totally out of date. mod_archive_odbc is not up to date too but it's better than mod_archive.
In a future post, I'll talk about the social aspect of my gsoc.
-
lundi 8 juin 2009 à 00:15:24
GSoC & me #1
It's been two weeks since I started the GSoC on Gajim. I chose to start with the roster versionning so I read the XEP-0237 the first week.
By and large, it's clear. I just regret that some points are not enough clear. By example when the server is sending us an iq without a query, it means that it will send us roster pushs to prevent us the changes between the version we have and the server one. But this iq doesn't let us to know if we have the last version and if we will receive roster pushs.
Another problem: when we must receive roster pushs, we have no idea on when excactly we received the last one. So we can't wait until we get the last to continue the connection procedure... For now I made the choice to consider the response iq (with or without query) at the roster request as enough to continue the connection procedure. The XEP says : ‘This specification is specifically designed to allow for a wide range of implementation choices’. So we have no other choice than to decide ourselves when some points are not covered.
Thanks to Matthew Wild and his jabber server written in Lua, called Prosody, I did some tests immediately in the Gajim XML console. I had a better understanding of the XEP after that.
With my mentor Asterix, we decided on a first draft about the way of storing the roster in the client side. Thats how I take one's first steps with sqlite and the Gajim configuration system (I knew that only with the Advanced Configuration Editor (ACE for friends)).
It's not inevitably permanent but that's how i do for now. I am storing the roster version key of each account in the Gajim configuration file (~/.gajim/config). Then i have a table which will store the different rosters inputs (the account jid key, the contact jid key, the name we gave to him, the subscription to the presence and the primary key on the first two fields) and the belonging to the group of each contact (the account jid key, the contact jid key, the group name and a primay key on those 3 fields).
For now the management of the version number is working wonderfully (it is sending well and updating it when there is some changes). I manage roster pushs too (as well at the table level that contains the roster inputs than for the groups).
The next big thing to do will be the management of the response iq when the roster is asking for it. I already found the place I will deal with and I have an idea on how to do it. Now I only have to do it (but it will have to wait until my exam week is finished (and it's starting today)).
-
jeudi 14 mai 2009 à 23:18:27
Google Summer of Code 2009
Hi English-speaking people. I have been selected to participate at the Google Summer of Code 2009. My mentoring organization is PSF, the project is Gajim and my mentor is Asterix (he can be found on the official Gajim room).
It is the first time that Gajim is not mentored by XSF because Peter Saint-Andre^W^WXSF decided not to participate this year. Despite this, there are twelve students that will work on XMPP this summer. So, I am one of them.
Let me introduce Gajim to you. Gajim is an instant messaging client for the XMPP protocol, written in Python and PyGTK. Year after year Gajim earns new features but it's still missing two very important which are very useful when you use your account with several clients and/or several computers and when you have a big roster. So you have chat logs in several places and that becomes a problem when you want to do a search. And when you have a lot of contacts, you have to wait for the server to send the full contact list, so you may have to wait until one minute before you can do something if your roster is very big. That is why I'm intending to develop server-side history and roster versioning for Gajim.
Gajim is no more my main XMPP client. For now it is jabber.el. So, why the hell do I work on Gajim? There are two reasons:
- I have used Gajim for several months. Despite the fact that I no more use it, it's always the XMPP client that I recommand to new users.
- I reported several bugs (some on the BTS, others directly to Jim++ and/or to Asterix). I have organized a bug squashing party. And I also submited some patchs. (yeah, I have my name in the THANKS /o)
For those reasons, I think I am well situated for this. It is also an occasion for me to be involved a little more in a free software project which is not from me. Furthermore, Gajim is migrating to Mercurial. It is been a while I want to migrate my own projects from Subversion to Mercurial, to take advantage of a decentralized VCS, so it is the occasion for me to test Mercurial on a real project.
About the schedule, I plan to develop roster versioning from May, 23rd, to June, 17th and server-side history from June, 18th, to August, 17th.
To finish, I want to thank my mentor, Asterix, which will have to support me during three months. I also want to thank PSF to take Gajim under one's wing for this GSoC. So, thanks Asterix and PSF!
