how to go about "sight range" and "line of sight blocking" in tile-based game?

Newbie & Debugging Questions
#1

Hi guys,

I’ve been itching to build a game for years and have spent a long time planning all the features I want to implement and how it’s going to work. I just hope I can muster the technical expertise to go from paper to computer :slight_smile:

I would like to ask you guys about implementing a maximum sight range and line of sight blocking terrain in a tile-based game.

say I have my character at position 10,10. He should be able to see up to 5 squares away, simple. BUT I would like it to be in a circle around him like this:


x x x x - - - x x x x
x x - - - - - - - x x
x - - - - - - - - - x
x - - - - - - - - - x
- - - - - - - - - - -
- - - - - o - - - - -
- - - - - - - - - - -
x - - - - - - - - - x
x - - - - - - - - - x
x x - - - - - - - x x
x x x x - - - x x x x

How would you go about dynamically generating this map? I would like the sight range to be variable (so at night it couldbe reduced, some mobs might have higher or lower range, etc).

I thought about calculating it like a triangle - x squared + y squared = direct distance squared but calculating this 120 times (for a sight radius of 5) per frame per entity doesn’t sound like the best way to do it.
I worked out that I could fudge it a bit by pre calculating the entity’s vision range and valid tile ids when creating the entity but wouldn’t that then hog memory that I wouldn’t need to be keeping?

My next problem is how to calculate the vision range when a sight blocking object is present, like this:


x x x x - - - x x x x
x x x - - - - - - x x
x x x - - - - - - - x
x - - B - - - - - - x
- - - - - - - - - - x
- - - - - o - - B x x
- - - - - - - - - - x
x - - - B - - - - - x
x - - x - - - - - - x
x x x x - - - - - x x
x x x x - - - x x x x

I can’t even fathom where to beging on calculating which blocks behind a blocking piece we should hide!

I’m not looking for code as I would rather understand how the process should work and code it myself to show my understanding so any talk on the subject would be very helpful :slight_smile:

Many thanks for reading!

(P.s. I’m new here, please be nice)

#2

One method of computing lines of sight is via ray casting: http://www.redblobgames.com/articles/visibility/
https://www.google.com/search?q=ray%20casting%20line%20of%20sight

Just limit the maximum reach of the rays and you will have this effect.

#3

That raycasting page looks really good, thanks BurntPizza :slight_smile:

#4

Raycasting is the best and one of the most detailed ways to do it . To make it efficient its best to 1: only check what needs checking so only see that the verticies in view are being checked 2:Dont check every tile , I made this mistake it causes horrific lag simply check each corner vertex of the tile 3:Only render shadows from visible verticies , so there was a thread about this I believe but what you do is you run through your verticies and you check to see if they intersect when you try to calculate it , if it intercepts another tile (tile has vertex 1 and 2 as its corners and if our line goes through this) then we disgard it.

Hope that helped aswell.

#5

iterate all tiles on a line : http://www.java-gaming.org/topics/another-line-grid-intersection/33755/view.html

#6

http://www.roguebasin.com there is quite a lot of information here which you will find relevant.

#7

Well, I am super pumped with myself now :slight_smile:

Here, showing tiles in full vision range:

And showing just tiles we can see:

finally, showing my workings :wink:

You can see what I’ve done here, I created a Rectangle2D over a tile and drew a Line2D from the centre to the tile we are checking. If they intersect I check the intersected tile to see if it blocks Line of Sight. Job done.

I feel it’s not the quickest way though as it currently has a lot of loops over the area - once to eliminate out of range tiles, once over the in-range tiles, then again (per tile!) to check for intersections, then once more to do something with the “visible” tiles.

Phew!

#8

Yeah that doesn’t sound efficient, but it’s pretty great I’d say for someone with a month experience. Congratz on a workable solution.

#9

Nice work. You might want to find a way to make those partially visible diagonals beside the wall be visible. One way to do that without extra processing may be to check the corners instead of the centers. I havnt thought about this much, but you may be able to assume, that if a corner point is not blocked, then all 4 tiles around it can be seen by the player. Another option is to check whether each of the 4 sides of a tile if visible (thats probably much less efficient though) but there, you can assume that if you can see at least one edge of a tile then that tile is visible to the player. Theres quite a few different methods available, but generally it is desirable to allow the player to be able to see around corners if they are close to a corner.

#10

Hmm, yes I see what you mean LiquidNitrogen. It is somewhat restricting at the minute.

I thought that to use the corners would add 3 extra checks, but I suppose I could check if we’re looking up and left then use the top-left corner, up and right use the top-right corner, etc.

I’ll give it a bash later. I called it done at this and moved on to movement so I could check how the framerate holds up with moving objects calculating their sight lines :slight_smile:

#11

Extremely good work however , you should do a check for the tile before you draw the ray to see if you are head to a wall tile or a floor tile.Also if you know that your ray already passes through a wall then you cant see anything and can cancel it.