This topic is now archived and is closed to further replies.


Looking for map-optimization algorithm

Recommended Posts

I think I am in the right forum for this, but don''t hesitate to relocate me if not. My game maps (2D and 3D) have a tendency to be based on square tiles. The map itself is not neccesarily sqaure, just each tile. Each tile may be solid, empty or anything in between, like diagonally divided. I define a wall tile as a solid tile that has at least 1 empty square in the 8 surounding squares. A trivial rendering loop (for 3D) would just draw all tiles on the map and leave visibility clipping to the graphics card. I obviously don''t want that. As the viewable area depends on where I am standing on my map, I would like to calculate (in advance, so it may take longer) the smallest rectangle containing all tiles viewable from this tile. I''d still have overhead, but greatly reduced. I know I could create the geometry, and make visibility checks on that, but I think it should be possible to take advantage of the fact that I am dealing with sqare tiles. Things I have stumbled over so far: - treat tiles as either solid, or non-solid ( 2 states) gives a larger region, sligthtly wrong, but good enough - visibility changes acording to where you are on the tile - a recursive algorithm using visibility sectors seems to be possible, just how exactly? BTW.: I would also be happy about any proof that this is NP-hard (though I don''t think it is) --------------------------- I may be getting older, but I refuse to grow up

Share this post

Link to post
Share on other sites