Quick 2D sight area calculation algorithm?

Filed under:
|
|
|
|
algorithm

I have a matrix of tiles, on some of that tiles there are objects. I want to calculate which tiles are visible to player, and which are not, and I need to do it quite efficiently (so it would compute fast enough even when I have a big matrices (100x100) and lots of objects).

I tried to do it with Besenham's algorithm, but it was slow. Also, it gave me some errors:

``````----XXX-        ----X**-     ----XXX-
[email protected]        [email protected]     [email protected]
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are
still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)
``````

I'm sure this can be done - after all, we have NetHack, Zangband, and they all dealt with this problem somehow :)

What algorithm can you recommend for this?

EDIT:

Definition of visible (in my opinion): tile is visible when at least a part (e.g. corner) of the tile can be connected to center of player tile with a straight line which does not intersect any of obstacles.

© Game Development or respective owner

Related posts about 2d

• Are high powered 3D game engines better at 2D games than engines made for 2D

as seen on Game Development - Search for 'Game Development'
I'm a software engineer that's new to game programming so forgive me if this is a dumb question as I don't know that much about game engines. If I was building a 2D game am I better off going with an engine like Torque that looks like it's built for 2D, or would higher powered engines like Unreal… >>> More

• 2D Array of 2D Arrays (C# / XNA) [on hold]

as seen on Game Development - Search for 'Game Development'
I want to create a 2D array that contains many other 2D arrays. The problem is I'm not quite sure what I'm doing but this is the initialization code I have: int[,][,] chunk = new int[64, 64][32, 32]; For some reason Visual Studio doesn't like this and says that it's and 'invalid rank specifier'… >>> More

• Need to know the origin and coordinates for 2d texture and 2d/3d vertices in webgl

as seen on Game Development - Search for 'Game Development'
Long story short, I know my coordinates are off and I believe my indices might be off. I'm trying to render a simple 2d rectangle with a texture in webgl here's the code I have for the vbo/ibo: rectVertices.vertices = new Float32Array( [ -0.5, -0.5, // Vertice 1, bottom / left 0.0, … >>> More

• USB packets - receive wrong data

as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
i have a little python script which shows me the packets of an enocean device and does some events depending on the packet type. unfortunately it doesn't work because i'm getting wrong packets. Parts of the python script (used pySerial): Blockquote ser = serial.Serial('/dev/ttyUSB1',57600… >>> More

• Php 2d array as C# 2d array/struct

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm using MailChimp's API to subscribe email to a list. Function listsubscribe() is used for email subscription: public static listSubscribe(string apikey, string id, string email_address, array merge_vars, string email_type, boolean double_optin, boolean update_existing, boolean replace_interests… >>> More

Related posts about engine

• Google App Engine - Figure out the time the current request reached the app engine

as seen on Stack Overflow - Search for 'Stack Overflow'
Is there a way I can figure out the time the current request reached the app engine? For example a user might make a request to my app, but due to app engine latencies my code might not start handling the request until one second later, is there a way I can figure out that the user has already… >>> More

• robocode engine: how to design (write) the runtime engine -- the robot world

as seen on Stack Overflow - Search for 'Stack Overflow'
IBM has (had) a free learn-Java program called RoboCode, in which custom robots could be written that would then do battle in a 2D space. I would like to write the environment that supports such robots, but don't know what pattern or design to use. Each robot is a thread. Each thread is given a… >>> More

• Search Engine Optimisation - Google Replaces Yahoo As T-Mobile's Default Search Engine

as seen on Ezine Articles - Search for 'Ezine Articles'
Competition has been stoked in the mobile search engine optimisation (SEO) sector with the announcement that Google is to replace Yahoo as T-Mobile's default engine. While T-Mobile USA has replaced Yahoo with Google as its default search on mobile phones such as RIM BlackBerrys, some Yahoo-based services… >>> More

• Search Engine Optimization Tips That Guarantee Your Webpage is Engine Program Friendly

as seen on Ezine Articles - Search for 'Ezine Articles'
The navigation links assists in determining the content in your web pages thus play a major role in search engine optimization. It is crucial that the keywords you use on your categories are easily identifiable by engine programs like... >>> More

• How to Improve Search Engine Ranking by On-Page Search Engine Optimization

as seen on Ezine Articles - Search for 'Ezine Articles'
There are two types of search engine optimization (SEO) techniques: on-page and off-page SEO. With on-page SEO, you have full control of all the techniques and methods you can use on your own sites. With off-page SEO, you will try some techniques to get other site owners to refer to your site which… >>> More