Author Topic: Good ways to do LoS  (Read 39874 times)

Vanguard

  • Rogueliker
  • ***
  • Posts: 1112
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #15 on: July 13, 2009, 08:26:29 AM »
Alright, well I found out what the problem was.

As usual, it was both something completely stupid, and in a place I didn't expect.

In Calculate.getSlope (of course it's one of the methods I didn't post here...) I used ints instead of doubles for the calculations, even though the return type is a double.  That meant that I would always get whole numbers for the slope and it messed things up.

Why is that always how it happens?

Anyway, the code I posted above works, so if anyone just does not want to bother with this or doesn't think they know how, it's up for grabs.

ido

  • Rogueliker
  • ***
  • Posts: 618
  • Karma: +0/-0
    • View Profile
    • Tame Tick
Re: Good ways to do LoS
« Reply #16 on: July 13, 2009, 08:28:01 AM »
Nice :)

Didn't your compiler warn you about assigning double to int?

-Ido.

Vanguard

  • Rogueliker
  • ***
  • Posts: 1112
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #17 on: July 13, 2009, 02:09:29 PM »
No, it didn't say anything, but I don't think it would with the way I wrote that method.  It looks like this in case you're curious:

    public static double getSlope(double firstX, double firstY, double secondX, double secondY) {
        return (secondY - firstY) / (secondX - firstX);
    }

Anvilfolk

  • Rogueliker
  • ***
  • Posts: 374
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #18 on: July 14, 2009, 10:02:39 AM »
You can still send int, and then multiply one number by 1.0. The compiler implicitly converts everything to doubles/floats :)

Also, doubles are really rather heavy. Do you need that kind of precision? Why not take floats? Doubles are 8 bytes, floats are 4, if I'm not mistaken.

Something like this should work, and be a little faster:

Code: [Select]
public static float getSlope(int firstX, int firstY, int secondX, int secondY) {
        return (1.0*secondY - firstY) / (secondX - firstX);
}
"Get it hot! Hit it harder!!!"
 - The tutor warcry

One of They Who Are Too Busy

Vanguard

  • Rogueliker
  • ***
  • Posts: 1112
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #19 on: July 14, 2009, 12:43:52 PM »
Hmm... yeah, it looks like you're right.  I changed Calculate.getSlope and the numbers within it as well as currentSlope to floats, and I don't notice any difference.  It's only... what, 20 bytes?  But I'll take it anyway.

Anvilfolk

  • Rogueliker
  • ***
  • Posts: 374
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #20 on: July 14, 2009, 09:09:12 PM »
I'm guessing it's normal that you don't notice it!

But when you're doing loads and loads of calculations on each step (for other kinds of games, where 3d needs to use that kind of stuff a bunch), it may eventually lag quite a bit. Anyway, CPU's nowadays are mostly 64 bits, so it shouldn't be that big of a difference... I just tend to use floats unless I need a high level of precision for whatever reason :)
"Get it hot! Hit it harder!!!"
 - The tutor warcry

One of They Who Are Too Busy

RantingRodent

  • Newcomer
  • Posts: 13
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #21 on: July 18, 2009, 05:00:31 AM »
I'm using a variant on a flood fill to handle LOS at the moment. For each tile traversed I store a list of directions to fill from that point. Each fill direction restricts 5 of the 8 cardinal directions from being filled from the destination tile. Tiles are processed in order of their distance from the source. If two tiles fill into the same tile, the restricted directions from that tile are only the directions restricted by both operations.

Any thoughts on this approach?

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Good ways to do LoS
« Reply #22 on: July 21, 2009, 07:15:11 PM »
That is technically much closer to raycasting than the above example.

Bad thing is that it doesn't work. I know, I just tried it.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Good ways to do LoS
« Reply #23 on: July 22, 2009, 10:07:51 AM »
I'm in the process of re-creating LOS for Kaduria. This is something I discovered in Teemu and it would be nice if someone has explanation for the problem. When traced to edges of levels (like in Teemu where the entire level is visible) the los is working, but when traced around the player in some distance the routine doesn't make symmetric LOS:

http://koti.mbnet.fi/paulkp/temp/kaduria3.jpg

purestrain

  • Rogueliker
  • ***
  • Posts: 172
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #24 on: July 22, 2009, 10:41:09 AM »
I guess your routine fails

Anvilfolk

  • Rogueliker
  • ***
  • Posts: 374
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #25 on: July 22, 2009, 12:04:39 PM »
It'll be hard just guessing if we don't have your algorithm here...

Either way, I'm betting on it being some sort of = where there shouldn't be one, like <= and >=... however, I find it weird that it happens in that situation!

It can also be what has been mentioned before: you're not considering the CENTER of each square, but rather the top-left corner or something along those lines :)
"Get it hot! Hit it harder!!!"
 - The tutor warcry

One of They Who Are Too Busy

Vanguard

  • Rogueliker
  • ***
  • Posts: 1112
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #26 on: July 22, 2009, 02:17:53 PM »
I'm in the process of re-creating LOS for Kaduria. This is something I discovered in Teemu and it would be nice if someone has explanation for the problem. When traced to edges of levels (like in Teemu where the entire level is visible) the los is working, but when traced around the player in some distance the routine doesn't make symmetric LOS:

http://koti.mbnet.fi/paulkp/temp/kaduria3.jpg


I have no idea if this will help in any way at all, since we don't have your code to look at, but I experienced a similar problem, and by changing the number comparisons it measures the slope against from a < and a > to a <= and a >= it seems to have been resolved.  Again, I have no idea if your stuff is similar to mine in any way at all, but that's what my problem was - the slope was exactly equal to, rather than greater than or less than the numbers it was measuring, so I got stuff like that.

Basically what I'm saying is that I had the problem Anvilfolk is suggesting might be the case with your problems, just in reverse.
« Last Edit: July 22, 2009, 06:13:05 PM by Curseman »

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Good ways to do LoS
« Reply #27 on: July 22, 2009, 02:58:02 PM »
It can also be what has been mentioned before: you're not considering the CENTER of each square, but rather the top-left corner or something along those lines :)

Something like that. Here is the routine:

Code: [Select]
int Fovmap::Round(float f)
{
return (int)(f+0.5f);
}

void Fovmap::Los_Line(int x1, int y1, int x2, int y2)
{
//check if source and destination positions are the same
if (x1==x2 && y1==y2) return;

int dx=x2-x1;
int dy=y2-y1;

int loop;
if (abs(dy)<=abs(dx)) loop=abs(dx);
else loop=abs(dy);

float x_inc=(float)dx/loop;
float y_inc=(float)dy/loop;

float x=(float)x1;
float y=(float)y1;

//origin point of los map coordinates
float fx=(float)origin_x;
float fy=(float)origin_y;

int rx, ry, tx, ty;
unsigned char b, c=fovVisible;

for (int i=0; i<=loop; i++)
{
x+=x_inc;
y+=y_inc;
fx+=x_inc;
fy+=y_inc;

rx=Round(x);
ry=Round(y);
tx=Round(fx);
ty=Round(fy);

if (c==fovVisible)
{
b=terrain->Get(rx, ry);

if (g_terrain[b].los>0) c=fovBlocked; //los in blocked from now on

Put(tx, ty, fovVisible); //use los map coordinates
explored->Put(rx, ry, 1); //use explore map coordinates
}
else Put(tx, ty, fovBlocked);
}
}

void Fovmap::Trace(int x, int y)
{
const int mw=Get_Width();
const int mw_half=(mw/2)-1;

//origin point is always visible
Put(x, y, fovVisible);
explored->Put(x, y, 1);

for (int o=x-mw_half; o<=x+mw_half; o++)
{
Los_Line(x,y, o, y-fov_len);
Los_Line(x,y, o, y+fov_len);
}

for (int o=y-mw_half; o<=y+mw_half; o++)
{
Los_Line(x,y, x+fov_len, o);
Los_Line(x,y, x-fov_len, o);
}
}

Vanguard

  • Rogueliker
  • ***
  • Posts: 1112
  • Karma: +0/-0
    • View Profile
Re: Good ways to do LoS
« Reply #28 on: July 23, 2009, 05:03:59 PM »
I spent the past day or so improving my LoS code I posted earlier.  It had some issues with how the LoS worked at the ends of hallways, but I think I've got them worked out.  I don't think the way I worked around it is especially pretty (from the standpoint of how the code looks), but it should be alright as to practical concerns.

Here's a link to the jar file so anyone who wants to take a look at the LoS code in action can do so.  I'd appreciate any comments and/or suggestions.

http://rapidshare.com/files/259173760/Guardian.zip.html

Everything is very much so a WIP.  There's no gameplay in there, the inventory and equipment screens are as bland as can be, and there's only one NPC who just follows ou around, but none of those things are the reason why I'm posting this.

Also, here is the updated code if anyone is interested:

    public void calculateFieldOfView() {
        initializeTileVisibility();
        for (int tileCounterY = 0; tileCounterY < Map.getStageSizeY(); tileCounterY++) {
            for (int tileCounterX = 0; tileCounterX < Map.getStageSizeX(); tileCounterX++) {
                // This will cut out unnecessary tiles to save processing time.
                if (tileCounterX < xLocation - lineOfSightRange) {
                    tileCounterX = xLocation - lineOfSightRange;
                }
                if (tileCounterY < yLocation - lineOfSightRange) {
                    tileCounterY = yLocation - lineOfSightRange;
                }
                if (tileCounterX > xLocation + lineOfSightRange) {
                    tileCounterX = Map.getStageSizeX();
                }
                if (tileCounterY > yLocation + lineOfSightRange) {
                    tileCounterY = Map.getStageSizeY();
                }
                if (Calculate.calculateLineOfSightDistance(xLocation, yLocation, tileCounterX, tileCounterY) <= lineOfSightRange) {
                    if (tileVisibility[tileCounterX][tileCounterY] == false) {
                        checkLineOfSightConnection(tileCounterX, tileCounterY);
                    }
                }
            }
        }
    }

    // This will check whether the character in question can see the location in question
    private void checkLineOfSightConnection(int xCoordinate, int yCoordinate) {
        Map currentLevel = Main.getCurrentLevel();
        // This will follow a path from the character's location to the destination point to see if there's something in the way.
        int scanX = xLocation;
        int scanY = yLocation;

        // This is marked as true if something is blocking the character's view
        boolean blocked = false;
        // This is the slope of the scanner's location measured against the destination.
        float currentSlope;
        // These are for dealing with the hallway issues.
        boolean firstMove = true;
        boolean limitHorizontal = true;

        tileVisibility[scanX][scanY] = true;
        if (this == Main.getPlayer()) {
            int tileType = currentLevel.getMapData(scanX, scanY);
            currentLevel.setMapMemoryData(scanX, scanY, tileType);
            tileLighting[scanX][scanY] = true;
        }

        // This will loop until the ray has reached its target, or is blocked by something;
        while (scanX != xCoordinate || scanY != yCoordinate) {
            // This is to ensure we don't get any divide by zero errors.  The slope is high enough that it'll work no matter what.
            if (scanX == xCoordinate) {
                currentSlope = 10000;
            } else {
                // We figure out what our current slope is, so we know how to reach our target.
                currentSlope = Math.abs(Calculate.getSlope(scanX, scanY, xCoordinate, yCoordinate));
            }
            // Now we use the slope to figure out how the scan coordinates should move.
            if (currentSlope <= 0.50) {
                if (scanX < xCoordinate) {
                    scanX += 1;
                }
                if (scanX > xCoordinate) {
                    scanX -= 1;
                }
                limitHorizontal = false;
            } else if (currentSlope >= 2.00) {
                if (scanY < yCoordinate) {
                    scanY += 1;
                }
                if (scanY > yCoordinate) {
                    scanY -= 1;
                }
                limitHorizontal = true;
            } else {
                if (scanX < xCoordinate) {
                    scanX += 1;
                }
                if (scanX > xCoordinate) {
                    scanX -= 1;
                }
                if (scanY < yCoordinate) {
                    scanY += 1;
                }
                if (scanY > yCoordinate) {
                    scanY -= 1;
                }
                firstMove = false;
            }
            // This is for resolving the problems I've been having at the ends of hallways.
            if (firstMove == true) {
                // We only need to do this if the target is more than one space away in both directions
                if ((Math.abs(xLocation - xCoordinate)) > 1 && Math.abs(yLocation - yCoordinate) > 1) {
                    int xTargetDirection;
                    int yTargetDirection;
                    int limitScanX;
                    int limitScanY;
                    boolean limitPov = false;
                    int targetDistance;
                    targetDistance = 0;

                    if (limitHorizontal == true) {
                        targetDistance = Math.abs(xLocation - xCoordinate);
                    } else {
                        targetDistance = Math.abs(yLocation - yCoordinate);
                    }
                    if (xLocation > xCoordinate) {
                        xTargetDirection = -1;
                    } else {
                        xTargetDirection = 1;
                    }
                    if (yLocation > yCoordinate) {
                        yTargetDirection = -1;
                    } else {
                        yTargetDirection = 1;
                    }
                    // This part checks to see if there are obstructions in the way.
                    // It moves diagonally starting at the player's location moving towards the target.
                    for (int obstructionDistance = 1; obstructionDistance <= targetDistance; obstructionDistance++) {
                        limitScanX = xLocation + (xTargetDirection * (obstructionDistance));
                        limitScanY = yLocation + (yTargetDirection * (obstructionDistance));

                        if (limitScanX >= Map.getStageSizeX()) {
                            limitScanX = Map.getStageSizeX() - 1;
                        }
                        if (limitScanX < 0) {
                            limitScanX = 0;
                        }
                        if (limitScanY >= Map.getStageSizeY()) {
                            limitScanY = Map.getStageSizeY() - 1;
                        }
                        if (limitScanY < 0) {
                            limitScanY = 0;
                        }
                        if (currentLevel.checkOpacity(limitScanX, limitScanY) == true) {
                            limitPov = true;
                        }

                        // These check either straight horizontal or vertical rows to see if the view is blocked.
                        if (limitHorizontal == true) {
                            if (limitScanY > yCoordinate) {
                                while (limitScanY > yCoordinate + obstructionDistance) {
                                    limitScanY += yTargetDirection;
                                    if (currentLevel.checkOpacity(limitScanX, limitScanY) == true) {
                                        limitPov = true;
                                        //xCoordinate = xLocation + xTargetDirection;
                                        limitScanY = yCoordinate;
                                    }
                                }
                            } else {
                                while (limitScanY < yCoordinate - obstructionDistance) {
                                    limitScanY += yTargetDirection;
                                    if (currentLevel.checkOpacity(limitScanX, limitScanY) == true) {
                                        limitPov = true;
                                        //xCoordinate = xLocation + xTargetDirection;
                                        limitScanY = yCoordinate;
                                    }
                                }
                            }
                        } else {
                            if (limitScanX > xCoordinate) {
                                while (limitScanX > xCoordinate + obstructionDistance) {
                                    limitScanX += xTargetDirection;
                                    if (currentLevel.checkOpacity(limitScanX, limitScanY) == true) {
                                        limitPov = true;
                                        //xCoordinate = xLocation + xTargetDirection;
                                        limitScanX = xCoordinate;
                                    }
                                }
                            } else {
                                while (limitScanX < xCoordinate - obstructionDistance) {
                                    limitScanX += xTargetDirection;
                                    if (currentLevel.checkOpacity(limitScanX, limitScanY) == true) {
                                        limitPov = true;
                                        //xCoordinate = xLocation + xTargetDirection;
                                        limitScanX = xCoordinate;
                                    }
                                }
                            }
                        }

                        // Now if we do find something blocking the way, we move the target coordinates in to better simulate real LoS.
                        if (limitPov == true) {
                            // First we do this so the loop ends.  There's no reason to keep it going.
                            obstructionDistance = targetDistance;
                            // Now we move the target coordinates appropriately.
                            if (limitHorizontal == true) {
                                xCoordinate = limitScanX;
                            } else {
                                yCoordinate = limitScanY;
                            }
                        }
                    }
                }
                firstMove = false;
            }
            // If the ray hits something opaque, we set blocked to true so the ray stops.
            if (blocked == false) {
                tileVisibility[scanX][scanY] = true;
                if (this == Main.getPlayer()) {
                    int tileType = currentLevel.getMapData(scanX, scanY);
                    currentLevel.setMapMemoryData(scanX, scanY, tileType);
                    tileLighting[scanX][scanY] = true;
                }
            }
            if (currentLevel.checkOpacity(scanX, scanY) == true) {
                blocked = true;
            }
        }
    }

// This sets every tile to unseen to start the turn out.
    private void initializeTileVisibility() {
        for (int yCounter = 0; yCounter <
                Map.getStageSizeY(); yCounter++) {
            for (int xCounter = 0; xCounter <
                    Map.getStageSizeX(); xCounter++) {
                tileVisibility[xCounter][yCounter] = false;
                if (this == Main.getPlayer()) {
                    tileLighting[xCounter][yCounter] = false;
                }

            }
        }
    }

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Good ways to do LoS
« Reply #29 on: July 25, 2009, 09:53:31 AM »
You can still send int, and then multiply one number by 1.0. The compiler implicitly converts everything to doubles/floats :)

Also, doubles are really rather heavy. Do you need that kind of precision? Why not take floats? Doubles are 8 bytes, floats are 4, if I'm not mistaken.

Something like this should work, and be a little faster:

Code: [Select]
public static float getSlope(int firstX, int firstY, int secondX, int secondY) {
        return (1.0*secondY - firstY) / (secondX - firstX);
}

Floating point arithmetic (on current x86 processors) is done on the FPU which internally uses 'double' or 'long double' floating point types (I am not sure which ones) -- and you don't require the new 64 bit processors for that, it was so for a long time on 32 bit processors. There is no reason to use singles (floats), it could actually make your program slower because it requires to convert the internal type to float. Thus, use doubles, unless you really care about space usage and floats' bad precision is sufficient for you.

You can also name your floating point type somehow, use this name everywhere in your program, and do some benchmarks yourself easily by changing this type (you can also port to a new hardware easily). My simple test program works in 0.56 s for doubles and long doubles, and in 1.21 s for floats. (This was a really simple calculation, not any real useful stuff.) Remember to turn optimization on.

Unless you need the floating point (i.e. you don't know the magnitude of the numbers you are working on), you can also try avoiding floats altogether and use integers only... this has some advantages (as they are easier to understand, you won't be hit by unexpected rounding errors; also testing for equality actually working).