One of the simplest algorithms in any roguelike is line of sight (LOS). It's basically drawing a line from one point to another and seeing if anything obscures it. Here's an Actionscript implementation of the Bresenham line algorithm (invented in 1962!).
It's not super obvious what's going on. Basically, figure out which direction the line always goes, and how often it goes in the other axis. Then go.
This is the basis for simple field of view (FOV) algorithms and is a quick and easy way of seeing if a tile, item, monster, or event can be seen by the player or another creature. It can also be used to calculate where a projectile will go, corridor generation, or simple pathfinding in open spaces.
I'm sure there are low-level ways to make this perform faster like bit shifting or breaking each octant into it's own function. It could also return an iterator that calculates points as-needed. This would allow really long lines - or even infinitely long lines - while only calculating what's actually needed.
No comments:
Post a Comment