Previously, on Bob and Trev: Resurrection...

...

Yeah, looks like I forgot to write anything to lead onto this article.

Anyhoo, this article will be discussing visibility and pathfinding. Both are important aspects of many roguelikes, and both have some important implementation issues to try and overcome. Line-of-sight algorithms are a popular topic on rgrd - right now I can see two threads talking about LOS algorithms, and know of at least one other that talks about them.

Line of sight

A roguelike typically uses a line-of-sight algorithm to calculate what the player can see, what monsters can see, and what should get hit by any area-of-effect events such as explosions. There are many different algorithms available, from brute-force ray casting, to the more optimised recursive shadow casting, or highly-specialised routines which rely on certain dungeon layouts. Although fast routines obviously run faster, they are also likely to take more memory - either in terms of code or data. Since I initially thought my largest enemy was code size, I started off with a brute-force ray caster.

The algorithm

The algorithm scans from the player outwards, in the shape of a series of concentric squares, as follows:

6666666666666
6555555555556
6544444444456
6543333333456
6543222223456
6543211123456
654321@123456
6543211123456
6543222223456
6543333333456
6544444444456
6555555555556
6666666666666

For each square in the sequence, a line is traced from the player to each point on the edge of the square. If the line makes it all the way to the end without hitting a solid object, the square is marked as being visible. So far, this is the same as a regular brute-force algorithm, apart from using a radial scanning order. The optimisation I've applied relies on this new scan order - for each radius, a set of flags are kept, indicating, for each side of the square, whether there was any tile that was visible. If no tile was visible on that edge during the previous iteration, then the algorithm assumes that no tile will be visible this time, either. When it reaches the state of no tiles being visible on any of the edges, the algorithm will terminate.

So far I've only using simple floating-point differentiation to walk trace the lines. A more advanced routine would use Bresenham's algorithm, which will be many times faster. But, I suspect, not fast enough - the floating point version takes around 40-60 seconds to run on a BBC. And since it has to be performed after every movement the player makes, it's obviously far too slow for a playable game.

Visibility, MK 2

After panicing for a while and debating whether to change to another algorithm or produce an assembler version of the current one (most likely post-challenge), I came to my senses and realised there was a much simpler approach I could take. My dungeon (currently) consists of a series of rectangular rooms. If I treat doors as vision blockers (even when they're open), then the player's visibility will be limited to just the room that he's in. This means two things:

1. Visibility information only needs to be recalculated when the player changes rooms (i.e. moves outside the currently visible area)
2. Calculating what's visible is just a case of finding the bounds of the current room

Unfortunately the map generator disposes of the room list after it's finished making the map, so there's no direct way of finding the coordinates. But since the rooms are (currently) rectangular, finding their bounds is just a case of tracing 4 lines out from the player in the 4 cardinal directions. There are a couple of situations where the algorithm gets fooled into producing the wrong results (e.g. if the player moves from a visible door to an invisible door - instead of providing visibility for one whole room, it will provide visibility for half of two rooms), but overall the tradeoff was worth it. Now in its fully optimised state, it only takes 3-10 seconds to change room. 90% of that time is spent in screen updates, so the delay isn't too bad - it's clear to the user that the computer is doing something and hasn't hanged.

Pathfinding

Pathfinding will be used for monster movement. Without pathfinding, the monsters won't be able to follow the player very well if he tries running away. There are basically three approaches available to me:

Algorithm	Accuracy	Speed	Memory usage	Code size
A*	Perfect	Medium	High	Low
Breadth-first	Perfect	Slow	Medium	Low
None	Low	Fast	None	Low

Of the accurate algorithms, A* is definitely the fastest, but requires the most memory. Memory which is unlikely to be available. Breadth-first requires less memory, and can be used to build a map of the entire level, pointing the monsters towards the player - so will become faster as more and more monsters use it. The algorithm entitled 'none', however, only uses simple comparisons to try and guide the monsters towards the player. E.g. if the player is to the east, walk to the east. A couple of extra rules can be used to try and guide the monsters round walls or through doors, but that's about it. It definitely has the speed advantage, however - there is no route map to rebuild every time the player moves.

Since the dungeon is fairly simple in construction, and my memory requirements are so tight, I'll be using the 'none' algorithm. Currently, this involves just sending the monster towards the player, trying to head in a vaguely correct direction if it bumps into something, and then trying a random direction if that doesn't work.

Next time

..I will be tackling combat. Having never written a roguelike combat system before, it will be an interesting exercise in deciding how mechanics such as strength and armour class will work, and attempting to get the numbers right first-time to reduce the amount of balancing required.