“If I have not seen as far as others, it is because
giants were standing on my shoulders.”
– Hal Abelson
I implemented a line of sight algorithm for Witherwyn last night. It works like this:
1. Given observer position (x,y) and r, the maximum range of vision, find all tiles on the map within distance r from (x,y).
2. For each of these tiles, do a ray trace with Bresenham’s line drawing algorithm to determine which of the potentially visible set are actually visible.
This naive approach to LOS is O(n^3). The constant factors, however, are all very small. I found a line rasterization routine from the days of the 33 Mhz Pentium DX. On that ancient hardware, it could do 5000 lines/second. R for my purposes is usually less than 20. So it seems like this is fine for now. I’ll fix it if it turns out to be broken or if the guy from rec.games.roguelike.development gets back to me about his spiral path algorithm.
Here’s a screenshot:
The next thing to work on, I think, it reworking how I handle different types of entities in my game. None of the classes I’ve taken at Stanford really talk about how to do object oriented design, so I’m finding it conceptually difficult to come up with a good, extensible paradigm for my game.
While it’s not playable yet, I think my game is getting to the point where others might be interested in looking at my source, so I’ll probably set up a dedicated page for it within the next couple of days.
Witherwyn Google Count: 2 – (local: 2, external: 0)
