Line of Sight for 2D grid-based games

Previous topic - Next topic

matchy

Alright! I suppose it would also work for a side-view platform game like a cavern level.

Ian Price

I'd give you two thumbs up, but you wouldn't be able to see, so here you go - :good: :good:
I came. I saw. I played.

Wampus

Quote from: matchy on 2011-Jun-02
Alright! I suppose it would also work for a side-view platform game like a cavern level.

Um, kinda. In theory it could be used for that but it would be prudent to only use it for a limited number of spawned entities, perhaps just the player character. Testing on a Intel Mobile 2 Duo 2.40GHz platform with a bad case scenario it takes only 75-77 entities with their line of sight set to 13 block radius (about right for a side-view platformer) to bring the refresh rate down below 60 FPS in a live action scenario. That's without much else but screen drawing going on. On slower machines like netbooks even 15 entities would be a lot.

It was designed as a luxury line of sight routine for turn-based games. To get really nice looking line of sight results its best to use something akin to ray tracing but that is very slow, requiring many thousands to many tens of thousands of rays to be calculated for each change in location/environment. My routine precalculates the results of ray tracing and uses some tricks to simulate a more realistic field of view than would be possible if strictly keeping to a single point of origin. Even with the tricks and precalcuated results its still requires a hefty chunk of CPU cycles.

For lighting effects in a side-view platform game it would be much faster to use a similar technique to something like Terraria. Crude though that method is, it is extremely quick.

Wampus

Ages ago I said I'd finished modifying my line of sight routine so that it could use limited angled arcs of light. Well, I never got around to writing up a simple demonstration routine to show what it was capable of. I also didn't complete the blast radius routine. I doubt I will get around to those things anytime soon since I've started work on a big project that I'm quietly excited about.

Anyway, attached to this post is the proggy that generates the precalcuated field of vision data. That way anyone can compile and see how far I got. The code is a bit of a nightmare but the app itself is somewhat self explanatory when in use. As far as I know the approach I took is unique. For comparison some others are shown here: http://roguebasin.roguelikedevelopment.org/index.php/Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

[attachment deleted by admin]