Jump to content
  • Advertisement


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


Looking for map-optimization algorithm

This topic is 5816 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!