Looking for map-optimization algorithm
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement