Elderlore

Source: Nolithius.com » roguelike

Back in my university days, I fondly recall when our professor for Structured Computer Organization, a seasoned computer scientist who worked on the EDSAC 1 back in the days of yore, asked, “Have any of you worked with Assembly?”. Having had the odd run-in with some flavors Assembly in previous microprogramming classes, I raised my hand.

He followed up the question with, “What’s the first thing that happens when you compile an Assembly program?”.

A notable silence followed, after which I answered, “It doesn’t work.”

“It doesn’t work!” he echoed, we laughed, and he segued into the day’s topic.

In a recent conversation in #rgrd, the oft-discussed topic of “to hack, or not to hack” came up. My stance on this topic is clear: do what you have to do to get it done. There exists a pervasive stigma in the developer community towards “voodoo code”, code that works, but you don’t know how or why. The reality of the matter is, my purpose is to program a game, not to figure out why ActionScript 3’s idiosyncratic handling of Numbers and ints caused the Bresenham code I lifted from RogueBasin and converted from C++ to misbehave on a very specific case!

Time that you spend cracking your head to optimize or understand a particular piece of code is valuable time that could be better spent developing! This approach must however be balanced with what Getting Real calls “paying back your programming debt”, that is, taking time as needed to clean up yesterday’s hacks for a better tomorrow. In following with this balance, I have devoted a small chunk of development time to rework some previously hacked code to make my life easier for the new features I am implementing.

Progress on Dance of Death continues strong. I have worked on the bulk of the goals for the next release, and have only a few (albeit large-ticket) items remaining. Version 0.3 will make an appearance within two weeks at most!

Source: If Error Throw New Brick

Another of the mini-goals of this iteration was to provide a "Welcome/Title" screen to magecrawl, allowing the player a place to enter a character name and choose between save files. As I might have mentioned before, this "attempt" at Magecrawl is not my first. I've written parts of my game before in C/C++/python before a settling on C#. My wonderful wife has heard more than one time about me

Source: If Error Throw New Brick

For those who've taken formal software engineering education or have programmed as a career, this post might something you've already heard of. However, I found myself coming back to this principle again while working on some code, and I figured it deserved a post nevertheless. DRY: "Don't repeat yourself". Originally formulated in Pragmatic Programmer (a great book I read as an intern), this

Source: If Error Throw New Brick

As previously mentioned, Magecrawl's 2nd tech demo was released yesterday. I received multiple reports of crashes during map generation. After some detective work, it became clear that all of the reporters were using non-English versions of Windows (Polish and French). This issue can be boiled down to this simple string: "10.0" In some languages, the period there is replaced with a comma. All

Source: If Error Throw New Brick

So the changelist that brought writing this post to mind was this one. I was working last weekend on Magecrawl, and decided that writing a "lightning bolt" like effect shouldn't be that hard. It just travels in a straight line until it hits a wall (or travels a maximum distance), hitting every creature in its way. In developing it, I violated a rule I try to follow in development both at home and

Source: If Error Throw New Brick

(Your regularly scheduled roguelike posts will continue after this brief announcement.) Magecrawl uses libtcod-net heavily both for graphics display and in the game engine (pathfinding, LOS, etc). libtcod-net is just a thin c# wrapper layer around libtcod that I wrote before starting Magecrawl.. I think for any new roguelike, written in either in a managed or unmanaged language, libtcod is a

Source: If Error Throw New Brick

So this story begins with a somewhat unexpectedly, I was working on map generator optimization (here) and rarely I'd hit an exception I wasn't expecting. The exception said I tried to generate a given level 10 times and failed. Digging into it further, the stitch map generator was having issues placing the required number of "chunks", coming up short the number I figure made decent map sizes. It

Source: Ascii Dreams

There are several approaches to allocating space for rooms for dungeon generation - Angband and variants use a cell based approach where the dungeon is divided up into 11x11 cells and then cells are marked as being filled when a room is placed which intersects the cell. The most common room size is 33x11 grids, or 3x1 cells, which was chosen because the space available in the Angband main screen was 66x22 grids on the majority of platforms it was ported to. The room sizes ensure that most rooms can be cleanly fit within the display.

A naive approach to placing the rooms is to pick a random top left-hand corner from 0 to dungeon_width - room width in cells, for the x-axis, and 0 to dungeon height - room height, again in cells, for the y axis. This approach is used in Angband and persists for the more sophisticated implementation used in Sangband (and I suspect Oangband and variants) in the find_space routine.

I've discovered several issues with find_space. The first is that space is never freed (cells marked as empty) if the room fails to be placed subsequent to find_space being called - easy enough to fix. But the one I want to talk about here is that the random approach fails significantly often - often enough for room placement to fail even when multiple attempts are made (25 per room in find_space).

My initial attempt to rectify this was to slide the room into an available space 'nearby' by moving it either horizontally or vertically a short distance and checking if it fit again. But this routine just highlighted how expensive multiple iterations within find_space was: making it 5 times more expensive (4 directions to test, plust the initial placement) resulted in a significant slow down in dungeon generation even on my Core Duo notebook.

I realised that there is one fact we know from attempting to place a room and failing that I could exploit: that the location we had tried was full. Sliding 'nearby' was counter-productive because nearby full was probably also full. So I should instead be looking as far away as possible, on the assumption that that would be empty.

The quickest way of doing far away as possible was to try reflection in either the x or y axis and try again. For checking grids near the midpoint, instead of reflecting, the code chooses either edge on that axis; basically a transformation from inner to outer. And to avoid checking the same far away multiple times, the code keeps choosing a random value for the axis that we don't transform - just like the original naive implementation.

To minimise calls to random, we just modulo the loop counter to determine which tactic to use, ensuring that the first time through the loop, as well as frequently enough in later iterations, we keep trying the naive approach.

This approach noticeably improved the success at placing rooms using find_room. It works well even if you don't randomly pick the position of the untransformed axis - because Sangband and Unangband attempt to place rooms from largest to smallest, I ended up with clusters of smaller rooms together, which had collided with a larger room in the originally attempted position, but could be placed near each other in the transformed position. I'm still undecided if I'll keep this artefact - it improves the dungeon aesthetic at a cost of requiring increased iterations to place rooms successfully.

As for moving to another placement method I've seen other coders use, such as binary subdivision, or even simulating playing Tetris, I want to keep compatibility with the original Angband code as much as possible, to keep this portable between variants.

Source: If Error Throw New Brick

Lately I've been thinking about "turn around time" and programming. I'd define this is the time it takes one a change is made to determine if it is correct. There are two parts to correctness: The syntax is correct and the compiler will accept it. The code "does what you want" The most important resource you have as a developer is your attention. The shorter this cycle is, the more likely you are

Source: If Error Throw New Brick

So, I'm still on an optimization kick. Map generation is still taking way too long, maps take too much memory. I figured I'd share this story, since it wasn't what I expected. So, I want the ability to have large levels, even if I don't use them. Say, 250x250, and maybe 50 levels total. My original data structure looked like: class Map {      private MapTile[,] m_map;      ..more.. } class