I have added a few more mandatory features:
'l'ook command now exists. Nothing more to say about that.
Monster memory has also been implemented. i.e., previously seen enemies show their last-seen location on the map when the player moves in such a manner that they are no longer in the line of sight. This is similar to how Crawl does it, except that the player is assumed to be able to recognize previously seen enemies, thus preventing a trail of characters from showing up representing the exact same monster.
Lastly, FOV now supports facing and actual field of view. The character is assumed to look in the direction they are moving, with a fairly generous FOV of 120 degrees. This is intended to change for characters 't'argeting a particular enemy, 'a'iming, or 'r'unning [to be implemented next...].
Tuesday, October 25, 2011
Sunday, September 25, 2011
Cave generation
After FOV, the next big aspect of the game to tackle was level generation.
For Ronin, the entirety of the game is intended to take place in underground caves, and hence I chose to adopt the most popular method for doing so, i.e. cellular automata, as described here and here. The latter link even includes a ready implementation in Python, though I chose to write one from scratch, both because I felt I could do some things better, and because I would otherwise need to adapt it to a hex grid and use my own level structures anyway. Furthermore, I needed the practice.
One side effect of generating levels using cellular automata is the possibility of forming "pockets", or areas of the dungeon that are disconnected from the rest. These are typically found using the disjoint-set structure, and this is what I did as well. The ready implementation mentioned also included a way for joining these pockets together, but for now I decided to just fill the pockets and regenerate the level with a new seed if the size of the dungeon is too small.
In other news, I may have finally ironed out all the bugs in the FOV code, caused by floating point inaccuracies. As a bonus, the FOV implementation now includes unit and regression tests, as well as an animated demo.
For Ronin, the entirety of the game is intended to take place in underground caves, and hence I chose to adopt the most popular method for doing so, i.e. cellular automata, as described here and here. The latter link even includes a ready implementation in Python, though I chose to write one from scratch, both because I felt I could do some things better, and because I would otherwise need to adapt it to a hex grid and use my own level structures anyway. Furthermore, I needed the practice.
One side effect of generating levels using cellular automata is the possibility of forming "pockets", or areas of the dungeon that are disconnected from the rest. These are typically found using the disjoint-set structure, and this is what I did as well. The ready implementation mentioned also included a way for joining these pockets together, but for now I decided to just fill the pockets and regenerate the level with a new seed if the size of the dungeon is too small.
In other news, I may have finally ironed out all the bugs in the FOV code, caused by floating point inaccuracies. As a bonus, the FOV implementation now includes unit and regression tests, as well as an animated demo.
Tuesday, August 23, 2011
Area Source Projecting Shadows Precisely and Asymmetrically (or, simply, ASP SPA)
One of the very first challenges I have decided to tackle was coming up with a Field of View algorithm that met my (rather particular) requirements.
Designing my own rather than picking one of the existing ones was not a decision I undertook lightly. There were several listed on roguebasin, and Restrictive Precise Angle Shadowcasting, as well as Precise Permissive Field of View were of particular note. However, I wanted something more than just a FOV algorithm. I wanted a solution that would also calculate cover for the purpose of lighting, and stealth and ranged combat mechanics.
There were several requirements. First, LOS needed to be symmetrical, i.e. if the target can see you, you can see the target. However, the amount by which each is seen can vary, to simulate, for instance, peeking around corners. In such a circumstance the actor doing the peeking would have a relatively slim chance of being spotted, and would benefit more from stealth, as well as having additional protection against ranged attacks. Second, it should work with both hex and square grids. Most existing algorithm implementations are designed for square grids, so this requirement made building one from scratch a good alternative. Third, it should not assume a point origin, but instead consider that the actors can be at any point in their respective tiles. This is a requirement that most current FOV algorithms do not meet, as they assume that the observer is at one point within a tile. It must be pointed out that Permissive Field of View does consider this, but it still doesn't compute cover.
When trying to come up with something that would satisfy these requirements I have hit a number of dead ends. One that worked rather well was a sampling approach. It would draw segments through the observer's tile as well as each target tile within a certain radius that would be perpendicular to the angle of view. It would then place n points on each tile, and compute which of the n points of one tile were unobstructed from each of the other tile's points. This produced very pleasing and relatively accurate results even with n as low as 5, and had the benefit of computing FOV for both tiles. The downside was that it was painfully slow, though this was partially due to the implementation being done in Python. With 5 sample points and a radius of 6 (distance computed as sqrt(x^2+y^2+xy) in hex coordinates) it would take at least a minute. With more points it would take considerably longer. While rewriting it in C++ would probably make the performance tolerable, I felt that I could arrive at a solution that would scale much better, without resorting to sampling and thus being more accurate.
My answer lay in vector algebra, and relied on the properties of the cross product of two vectors. In particular, the cross product of two vectors is negative if the second vector is to the right of the first, and positive if it is to the left. Moreover, by constructing a unit vector coming from the observer and crossing it with the vector to the target, the amount by which it is off can be directly translated into the amount of cover! To clarify, by representing the shadow-projecting area source as a pair of unit vectors positioned on the circumference of the observer's tile, we can treat any tile as covered if it is fully covered by the area that is bound by these two vectors. That is, if the target tile is fully left of the right-side vector, and fully right of the left-side vector, then we know it is fully in cover. Similarly, if the cross product of either of the unit vectors with the respective sides of the target tile has a magnitude between 0 and 1, we know we have partial cover. The computations get a little tricky with angles approaching 180 degrees and also reflex angles, but this is basically the gist of it. The algorithm mostly involves iterating over tiles arranged by distance, and forming new -- or extending existing -- vector pairs from any tiles that are construed as walls, i.e. block line of sight. The algorithm is relatively slow for a "forest" of tiles with infinite sight radius, but fairly quick for a more cave-like structure. By migrating the entire algorithm into C-land and adding caching further performance gains could be reached, while maintaining an extremely precise cover calculation mathematically.
Here's a screenshot of the FOV in action, also showcasing the (unoriginal) cave generation algorithm (to be discussed later).
Designing my own rather than picking one of the existing ones was not a decision I undertook lightly. There were several listed on roguebasin, and Restrictive Precise Angle Shadowcasting, as well as Precise Permissive Field of View were of particular note. However, I wanted something more than just a FOV algorithm. I wanted a solution that would also calculate cover for the purpose of lighting, and stealth and ranged combat mechanics.
There were several requirements. First, LOS needed to be symmetrical, i.e. if the target can see you, you can see the target. However, the amount by which each is seen can vary, to simulate, for instance, peeking around corners. In such a circumstance the actor doing the peeking would have a relatively slim chance of being spotted, and would benefit more from stealth, as well as having additional protection against ranged attacks. Second, it should work with both hex and square grids. Most existing algorithm implementations are designed for square grids, so this requirement made building one from scratch a good alternative. Third, it should not assume a point origin, but instead consider that the actors can be at any point in their respective tiles. This is a requirement that most current FOV algorithms do not meet, as they assume that the observer is at one point within a tile. It must be pointed out that Permissive Field of View does consider this, but it still doesn't compute cover.
When trying to come up with something that would satisfy these requirements I have hit a number of dead ends. One that worked rather well was a sampling approach. It would draw segments through the observer's tile as well as each target tile within a certain radius that would be perpendicular to the angle of view. It would then place n points on each tile, and compute which of the n points of one tile were unobstructed from each of the other tile's points. This produced very pleasing and relatively accurate results even with n as low as 5, and had the benefit of computing FOV for both tiles. The downside was that it was painfully slow, though this was partially due to the implementation being done in Python. With 5 sample points and a radius of 6 (distance computed as sqrt(x^2+y^2+xy) in hex coordinates) it would take at least a minute. With more points it would take considerably longer. While rewriting it in C++ would probably make the performance tolerable, I felt that I could arrive at a solution that would scale much better, without resorting to sampling and thus being more accurate.
My answer lay in vector algebra, and relied on the properties of the cross product of two vectors. In particular, the cross product of two vectors is negative if the second vector is to the right of the first, and positive if it is to the left. Moreover, by constructing a unit vector coming from the observer and crossing it with the vector to the target, the amount by which it is off can be directly translated into the amount of cover! To clarify, by representing the shadow-projecting area source as a pair of unit vectors positioned on the circumference of the observer's tile, we can treat any tile as covered if it is fully covered by the area that is bound by these two vectors. That is, if the target tile is fully left of the right-side vector, and fully right of the left-side vector, then we know it is fully in cover. Similarly, if the cross product of either of the unit vectors with the respective sides of the target tile has a magnitude between 0 and 1, we know we have partial cover. The computations get a little tricky with angles approaching 180 degrees and also reflex angles, but this is basically the gist of it. The algorithm mostly involves iterating over tiles arranged by distance, and forming new -- or extending existing -- vector pairs from any tiles that are construed as walls, i.e. block line of sight. The algorithm is relatively slow for a "forest" of tiles with infinite sight radius, but fairly quick for a more cave-like structure. By migrating the entire algorithm into C-land and adding caching further performance gains could be reached, while maintaining an extremely precise cover calculation mathematically.
Here's a screenshot of the FOV in action, also showcasing the (unoriginal) cave generation algorithm (to be discussed later).
Saturday, March 12, 2011
Design Decisions: Grid type.
First of all, this blog is not dead. There has been a lot of work going on the implementation of Lorem Ipsum I (as the roguelike is now going to be called).
One of the decisions most roguelike developers never have to face is how to lay out their tiles, and what shape they will be. Given the constraint of working with curses, the choice of a rectangular grid with square -- well, rectangular of 2x1 dimensions -- tiles is an obvious one. Rectangular grids pose many advantages:
The layout also happens to be surprisingly easy -- working with monospace fonts of 2x1, successive columns can be staggered by half a tile's height presenting a pseudo hexagonal grid which looks pretty damn good. For greater effect, I have included an option to offset the columns away from each other by a factor of 1.75, which approximates the distance between actual hexagonal tiles. While this wastes some screen real estate, the outcome looks particularly even as a result.
Here is an image showcasing a hexagonal grid, as well as the new FOV algorithm (to be discussed later):
One of the decisions most roguelike developers never have to face is how to lay out their tiles, and what shape they will be. Given the constraint of working with curses, the choice of a rectangular grid with square -- well, rectangular of 2x1 dimensions -- tiles is an obvious one. Rectangular grids pose many advantages:
- Rectangular grids lend themselves naturally to rectangular rooms in a dungeon map, for an easy correspondence to the real world;
- Similarly they promote 90 degree angles in corridors, which is also quite natural;
- They are easy to visualize and describe -- for that matter they may be effectively stored in a text file, either for a saved game or for a post-mortem character dump;
- As has been mentioned before, they are the only sensible choice when working with curses;
- Most computations get easier, for instance distance between tiles is trivial to compute, as the square root of x^2+y^2.
- Using curses and monospace fonts, visually the distance between horizontal and vertical tiles is off by a factor of two. This is a result of most monospace fonts being 2x1;
- Worse yet, diagonal distances are off by a square root of two, and the developer is left with an uncomfortable task of reconciling what that will mean in game terms. Common approaches involve assuming that diagonal movement is as expensive as that along the axes (which distorts distance favoring diagonal movement), or treating it to be 1.5 times as expensive (a crude approximation of the square root of two, but generally functional), which also entails tailoring the game to support 'fractional' movement;
- On the same note, rectangular grids mean a player character can be surrounded from 8 sides... with four of the sides being a different distance 'off', potentially;
- Lastly, rectangular grids make line of sight and field of view algorithms harder. For instance, if two 'wall' tiles are touching on a diagonal, do they block line of sight? Why or why not?
The layout also happens to be surprisingly easy -- working with monospace fonts of 2x1, successive columns can be staggered by half a tile's height presenting a pseudo hexagonal grid which looks pretty damn good. For greater effect, I have included an option to offset the columns away from each other by a factor of 1.75, which approximates the distance between actual hexagonal tiles. While this wastes some screen real estate, the outcome looks particularly even as a result.
Here is an image showcasing a hexagonal grid, as well as the new FOV algorithm (to be discussed later):
Wednesday, January 26, 2011
Design Decisions: Choosing an output library.
When developing in Python, the options for the output are rather limited -- only curses and SDL (via pygame) are available. In theory there's also libtcod, which sits on top of pygame, but despite how much it touts being cross-platform unlike straight up pygame it refuses to work on 64-bit OS X, making it a poor choice for this particular developer.
Of the remaining two, curses is easier to use and is, in theory, more cross-platform. It opens up the option to run the game in any terminal, in screen or over ssh. It could then conceivably be adapted to run via dgamelaunch -- a definite plus. Now, the downsides: the output is entirely at the mercy of the terminal, and there may need to be specific code changes to enable the game to display properly on any available terminals. It also leaves it up the user to properly configure their terminal colors, and furthermore the color options are going to necessarily be limited to xterm-colors to allow for widest support.
Pygame, on the other hand, is more challenging to develop for, as it deals with images rather than characters. Hence, more aspects of the game would need to be written from scratch. The benefits are huge, however -- cross platform compatibility ends up actually being greater, even as far as (in theory) running on Android devices. Additional huge pluses are: ability to have hexagonal grids (which is something I have been seriously considering), and a multitude of colors for greater gradations (important when lighting has significant in-game implications).
For now the winner is clearly pygame.
Of the remaining two, curses is easier to use and is, in theory, more cross-platform. It opens up the option to run the game in any terminal, in screen or over ssh. It could then conceivably be adapted to run via dgamelaunch -- a definite plus. Now, the downsides: the output is entirely at the mercy of the terminal, and there may need to be specific code changes to enable the game to display properly on any available terminals. It also leaves it up the user to properly configure their terminal colors, and furthermore the color options are going to necessarily be limited to xterm-colors to allow for widest support.
Pygame, on the other hand, is more challenging to develop for, as it deals with images rather than characters. Hence, more aspects of the game would need to be written from scratch. The benefits are huge, however -- cross platform compatibility ends up actually being greater, even as far as (in theory) running on Android devices. Additional huge pluses are: ability to have hexagonal grids (which is something I have been seriously considering), and a multitude of colors for greater gradations (important when lighting has significant in-game implications).
For now the winner is clearly pygame.
Thursday, January 13, 2011
Design Decisions: Picking a language.
Ultimately I have managed to boil it down to two choices -- C++, and Python. While Lua is popular lately and would open up the opportunity for me to use the TOME library, I chose not to spend the time to learn a different language when I can focus on improving my expertise in a language I can use for work.
Between the two, C++ offers the advantage of static typing, and, as a result, a more rigid development structure that may be of benefit as the project gets larger. Python, on the other hand, offers rapid development and a pleasant and intuitive syntax. I have settled on using Python for now and perhaps delegate any potential computationally intensive processing to a C++ library I can always introduce. Pyrex was considered, but for the time being not thought necessary.
Between the two, C++ offers the advantage of static typing, and, as a result, a more rigid development structure that may be of benefit as the project gets larger. Python, on the other hand, offers rapid development and a pleasant and intuitive syntax. I have settled on using Python for now and perhaps delegate any potential computationally intensive processing to a C++ library I can always introduce. Pyrex was considered, but for the time being not thought necessary.
A trivial roguelike.
Created a trivial roguelike using python + pygame. It is completely useless as a game, but could be a good starting point for someone else trying to write something in the genre.
https://github.com/megawidget/trapped
https://github.com/megawidget/trapped
Subscribe to:
Posts (Atom)