[Beginner] Strange shadowcast

[Hundertzehn]

Hello!

I just started to program a roguelike, and I ran into a problem with my shadowcast. Perhaps someone can help.
(This is only 1/8 of a shadowcast so far, so only one octant)

This is what happens:
(@ = player, S = shadow, . = visible, # = wall)

Code: [Select]

@......
S......
S##S...
SSSSS..

When I move closer to the wall, I can see around the corner:

Code: [Select]

SSSSSSS
@......
S##....
SSSSSS.

Similar behaviour occurs in similar situations. Can someone give me a hint what might be the case?

The relevant code:

Code: [Select]

def shadowcast(self,start_slope, end_slope, dx):
        # iterative shadowcast
        if dx < 30: #30 is the maximal range of vision
            # dx is the distance from the @ the current iteration is looking at           
           
            # a few renames for our convenience           
            pc_x = PC.position[0]
            pc_y = PC.position[1]
           
            original_end_slope = end_slope           
           
            # calculate the starting point of this column
            starting_point = int(math.floor(start_slope*dx))
           
            # checks if the starting point is still on the map           
            if (starting_point + pc_y) > (MAP_HEIGHT - 1):
                starting_point = (MAP_HEIGHT - 1) - pc_y
               
            end_point = int(math.ceil(end_slope*dx))
           
            # does the calculation for the column start with a blocked los?
            prior_blocked = map.content[pc_x + dx][pc_y + starting_point].block_los
           
            # some cosmetic changes. Make more walls visible
            cosmetic_y = starting_point + 1
            if (pc_y + cosmetic_y) < (MAP_HEIGHT):
                if (map.content[pc_x+dx][pc_y + cosmetic_y].block_los):
                    if not(map.content[pc_x+dx-1][pc_y + starting_point].block_los):
                        map.content[pc_x+dx][pc_y + cosmetic_y].visible = True           
           
            for dy in range(starting_point, end_point-1, -1):
                # The tile that is checked               
                tile_x = pc_x + dx
                tile_y = pc_y + dy
                # every tile checked is visible, or we wouldn't check it.               
                map.content[tile_x][tile_y].visible=True
               
                # If we go from unblocked to blocked, new end_slope is
                # calculated and recursive call is executed               
                if (not prior_blocked) and map.content[tile_x][tile_y].block_los:
                    end_slope = (dy+.5) /float(dx-.5)
                    if (tile_x+1)<MAP_WIDTH:
                        # Recursively continue to calculate
                        self.shadowcast(start_slope, end_slope, dx+1)
                    prior_blocked = True
               
                # If we geo from blocked to unblocked, a new start_slope is
                # calculated for later recursive calls
                if prior_blocked and (not(map.content[tile_x][tile_y].block_los)):
                    start_slope = (dy+.5) /float(dx+.5)
                    prior_blocked = False
           
            # if we are still on the map, recursively calculate the next column
            if (pc_x+dx+1)<MAP_WIDTH and (not map.content[pc_x+dx][pc_y+end_point].block_los):
                self.shadowcast(start_slope, original_end_slope, dx+1)


[Krice]

There is something odd in those shadow parts. Sure you got them right? Anyway, the reason for aliasing problems is the coarseness of the routine when it's 1:1 which is often the case. Line drawing or whatever goes only one of the two ways and it may be the "wrong" way. Also it changes over the distance and slope. How to fix it in this case I'm not sure.

[mushroom patch]

Previous comment withdrawn, I misread the code.

[reaver]

Here's a working implementation of what you're trying to do, so you can compare.

http://www.roguebasin.com/index.php?title=FOV_using_recursive_shadowcasting_-_improved

[Hundertzehn]

Thanks for your replys. I didn't find the bug, but decided to change to a circle-based shadowcast. It is already working and almost bug free. No strange behaviour this time! 

[Hundertzehn]

Tada:


I like it so far.

Now I have to decide if I continue with monsters or with items...

[Hundertzehn]

I'm back to the shadowcast. The devil is in the details. I have one case (really, eight cases because of symmetry) where a tile that should be invisible is visible. I know exactly why that is so - the computer just does what I tell him to do - but I have no idea for an elegant solution...

[Hundertzehn]

In my circular shadowcast, there are a few cases where it is possible that one tile is blocked by an other tile with the same (integer value) radius. I didn't check for that, but just assumed that tiles could only be blocked by tiles with a smaller (integer value) radius. One additional check later, all seems fine!