Author Topic: Screenies of LOS :3  (Read 11000 times)

honey_spider

  • Newcomer
  • Posts: 12
  • Karma: +0/-0
    • View Profile
Screenies of LOS :3
« on: February 13, 2013, 02:31:48 AM »
Hey everyone!  It has been a couple of months since my last post, but I thought I would share my first real success.
 
http://imgur.com/a/Pd4iy
 
The link above shows my line of sight in action, as best I could represent it with a few screenshots.  I would upload a working .exe but I can't think of anywhere that will let me host it ...and it would seem a little dubious at best.
 
I would like to share the code too ...the basics of which are Bresonhams in a format I grabbed from a blog linked from a thread at TIGsource (which I cannot find now), and a few modifications of my own.
 
 
https://gist.github.com/anonymous/4909278
 
 
I think I will write part of this into a function which I can call again for my aiming and so on -anywhere else I need to use LOS basically, which will save me re-writing heaps of code.
 
 
I hope this helps someone =]
 
 
The next challenge I have set myself is extending the map beyond the dimensions of the view window.  After that, it's random dungeon generation!
« Last Edit: February 13, 2013, 02:39:53 AM by honey_spider »

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Screenies of LOS :3
« Reply #1 on: February 13, 2013, 06:17:26 AM »
you can always host using dropbox

honey_spider

  • Newcomer
  • Posts: 12
  • Karma: +0/-0
    • View Profile
Re: Screenies of LOS :3
« Reply #2 on: February 13, 2013, 06:22:59 AM »
I suppose you are correct  ...though I have since decided running around my tiny little map is not fun at the moment.  The thing I really wanted to share was the code =]

Omnomnom

  • Rogueliker
  • ***
  • Posts: 79
  • Karma: +0/-0
    • View Profile
    • Email
Re: Screenies of LOS :3
« Reply #3 on: February 14, 2013, 12:25:17 AM »
nice,

What you've done is calculate the player's field of view using line of sight algorithm to calculate whether each tile on the map is visible to the player. This is what I did at first, I prefer this because it is intuitive and works fine and like you said it's a nice piece of code you can reuse for aiming.

But just a heads up about something you might encounter (hopefully not) because you mentioned making the map larger. Unfortunately I found the performance was too bad with larger maps, because as the width and height of the map increases the time taken to calculate line of sight of every tile exponentially increases. Also there is additional hit if you want to calculate monster FOVs too.

You might have no problem depending on how big maps you intend and whether you intend to calculate monster FOVs each turn. But just in case you hit this wall, there are algorithms specifically for calculating field of view that are more efficient and can handle bigger maps because they reuse information and avoid checking tiles behind obstructions. Unfortunately those algorithms range from complicated to absurdly complicated to implement.

The one I used (because it seemed the simplest, performs almost the best compared to others and seems accurate enough...) is:
http://roguebasin.roguelikedevelopment.org/index.php?title=FOV_using_recursive_shadowcasting

Unfortunately it's a bit of a mind-**** and took me weeks to understand it on paper before I could event attempt to implement it. Then it took me weeks more of bug tracing because I kept screwing up. In hindsight it would have been better to just understand it and then use someone else's code...

Just something to bear in mind if you find your turn-calculation takes too long with a larger map.

Although perhaps a better option (rather than wasting weeks on a more complicated algorithm) is to limit the maximum view range of the player so you don't need to calculate the visibility of all tiles on the map. The map could be infinite if the player can only see 20 tiles radius. A trick to largely hide this would be to make the map generator never (or rarely) generate huge open areas where the player would notice the restriction. Or just use the convenient excuse that the player is carrying a light source and it can reach go so far.

I know at least two years back when I last played it, minecraft was using a similar trick. Hugely inefficient, the client fetches entire 16x16x256 tile chunks from the server, even though the vast majority of those tiles are typically underground and the player can't see them. So they didn't spend time making a complex algorithm to only send the visible 3D tiles (if that's even possible), they just send them all (an unfortunate consequence of this is that people can create undetectable client x-ray hacks...). Then on the client I believe they just draw every tile and let the graphics api/driver/card deal with occlusion. They limit the performance hit (on the server and client) by putting in a shorter horizon view distance...although it's so short you often see the horizon loading in the distance. This is something that's always bugged be about minecraft from a purity point of view (plus the x-raying). Possibly there is something technical I don't understand which forces them to it this way. But on the otherhand the game was somewhat popular so it shows a complex algorithm isn't always necessary and tweaking things like view distance can work.


honey_spider

  • Newcomer
  • Posts: 12
  • Karma: +0/-0
    • View Profile
Re: Screenies of LOS :3
« Reply #4 on: February 14, 2013, 02:34:53 AM »
Thanks for the reply, I enjoyed reading it.  As for the view distance, I am going to limit it too the width of the viewable screen (which is at the moment MAPSIZE).  Once MAPSIZE increases, I will create a new constant called SCREENSIZE or something like that.
 
Also, the line is drawn from the player outward and the calculations stop when each line hits a wall.  The bad thing though, is that at the moment it begins tracing a line from the player to every tile on the map until that "break" happens ...meaning a LOT of tiles are checked more than once -in particular those closest to the player.
 
For the time being, I am not going to look into efficiency until it starts to have an effect on gameplay. 
 
As for mobs, I figure if the player can see them, then they can see the player.  I will develop that further if I ever need the mobs to interact with each other.
 
I thought I could be clever with my lightsource and make the variable "int n" = 3 for a light radius of 3 ...but that only makes a diamond shape around the character because of the way bresenhams draws lines.  I think therefore, I may have to write a completely new function for lamps and the like.  Surely it can't be too difficult to write an algorithm that will draw a circle with tiles.  If I get it right, I can use it in my mapgen too :3
 

Nymphaea

  • Rogueliker
  • ***
  • Posts: 74
  • Karma: +0/-0
  • Maria Fox
    • View Profile
    • Nymphaea.ca
Re: Screenies of LOS :3
« Reply #5 on: February 14, 2013, 12:26:28 PM »
Circle is done like so:
Code: [Select]
// '^' = "to the power of"
x^2 + y^2 = r^2
So figure out the radius(3 for you), then check every square within that square radius([player.x - 3,player.y - 3] to [player.x + 3,player.y + 3]) if it is true for the above equation or not, ones that return true are within the radius and should be lit up. I would suggest, though, before the loop you calculate 'r^2' and store it in a variable, so that's one less calculation you have to do each cycle :P

As for checking more than once, you could always have a boolean array, and only check the tile if it hasn't been checked yet.

Omnomnom

  • Rogueliker
  • ***
  • Posts: 79
  • Karma: +0/-0
    • View Profile
    • Email
Re: Screenies of LOS :3
« Reply #6 on: February 14, 2013, 09:03:39 PM »
The only thing I disagree with is pre-calculating r^2. I strongly disagree  :o. It's better to optimize after hitting performance problems than before, because it's hard to guess where the bottleneck will be (or even if there will be one). It might turn out r^2 doesn't need optimization. Then again maybe you know it will do, in which case sorry for butting in. But the lazy path of optimizing later not before has served me well so far ;D

Nymphaea

  • Rogueliker
  • ***
  • Posts: 74
  • Karma: +0/-0
  • Maria Fox
    • View Profile
    • Nymphaea.ca
Re: Screenies of LOS :3
« Reply #7 on: February 15, 2013, 01:39:59 AM »
It's just simple logic :P

Performing r^2 every loop is doing an extra multiplication each time, which can be reduced to a single time with just one line of code. On modern computers most people won't notice I'm sure, but if you use similar logic for multiple entities, then eventually it gets excessive. I do the same with if statements, calculate the right half of the condition( "if(int l=0;l<[this part];l++)" ) before the loop so it doesn't happen each time.


I just have a bit of an efficiency obsession :P I find most programmers ignore the small things because of modern computer speeds, but plenty of people(including me and people I know) still use older machines that fail run programs because of this.

Omnomnom

  • Rogueliker
  • ***
  • Posts: 79
  • Karma: +0/-0
    • View Profile
    • Email
Re: Screenies of LOS :3
« Reply #8 on: February 17, 2013, 03:46:53 AM »
I agree with optimization to get the program running on slower machines. Maybe r^2 and for loop optimizations are necessary for that, but it would bug me to add them without knowing that they really were needed.