Again a grid might be simpler as it makes resolving the visibility simple. It handles the collisions under the same basic ideas and its easy to implement. It has one more benifit in that the collision grid can be used seamlessly for A* path finding and variants of it that automatically contain weighting information.
A collision grid is very good for maps with a lot of non moving collide-able (static) objects like tons of walls ect.
if however you will have 10,000 ships moving at once that will be a lot of insertions and deletions and then it will suffer unless the grids are much larger then the ships themselves and these ships are spread out. In that case a quad tree will probably be better.
Eliminating broad phase collisions is not even (n) time with a simple grid in fact it can be considered 0 as in no time, as moving the object itself is the only thing that really costs, To say moving into a already occupied grid simply flips a bool and some id and grid number is added to a collision check result list. Insertion consists of adding a object to a number of collision grids or one same for removal and these are usually integer id placeholders to some object.
The grid size chosen makes a big difference for how much can be eliminated in a broad phase check and how fast or slow the algorithm handles moving objects these two factors are usually opposites. Such that tweeking the grid size alone can make a considerable performance difference with a grid.
The jist is simple with grids for both visibility and collisions.
you need to basically define a couple transformation methods.
WorldToMapTileIndex and the reverse
WorldToCollisionGrid and the reverse
you define the total size of your game world.
you define all your objects and tiles in 2d world space by the actual size of your game world.
you define all your tiles by there tile size in the world say 50x50 ectâŚ
you define the size of a collision grid say itâs world size say 125x125 whatever you want.
then
the total number of collision grids is world size / collision grid size.
(you get a bucket xy size to use for a bucket array)
the total number of map tiles is world size / tile size.
(same you get a total x y tile map size for a map array)
to find were a point is in your world, be it a character position or a map tile rectangle.
related to the collision grid space you do the following.
position / collision grids size
related to the tile grid space.
position / map tiles size.
To know what map tiles to draw you need to know the screen width and height.
the scroll position these positions can be found by a camera projection as well.
in a simple version well just increment or decrement x or y scroll values with arrow keys.
so you end up with a bounding rectangle that is your screen to world window.
you find the visible tiles by simply dividing that bounding rectangles values by the map tiles world width and height respectively. To get integer array coordinates in a new looping rectangle to the map arrayâŚ
You loop that visible map rectangle with a for x and for y loop and draw the map tiles at those stored locations to the screen by (x - loopingIndexRectangle.X) * tileWidth ect⌠to smooth the scrolling is fairly simple but i digress.
The entire process is very straight forward if you think of all aspects including were your screen is in relation to or within your virtual game world. Which as far as all your objects and even your screen is concerned are the only real coordinates that they all must relate to.
Maybe ill throw together a simple example class and post it.
If you like ?
and
if i have time, though it wouldnât take long, i donât know when ill have much free time for a few days.