Messages

1

Programming / Re: Need help to implement a Line-of-Sight algorithm for a roguelike in VB6

« on: August 06, 2008, 08:42:52 AM »

Hmmm...it seems like I need to study more about the order of what does what in this algorithm.

In the meanwhile, I toyed with a Recursive Shadowcasting FOV, found here:
http://roguebasin.roguelikedevelopment.org/index.php?title=FOV_using_recursive_shadowcasting_-_improved
which works alright, but has 1 major flaw which I don't know how to fix yet:

As you can see in the attachment (only the 1st octant is processed), behind a single obstruction, at some specific spots, the "shadow" line is not consistent. So behind eg. a pillar, other tiles are visible while others are not. This happens especially when the obstruction tile approaches the y-axis. The code (for the 1st octant only) is:

Code: [Select]

Public Sub RecursiveVisibility(px As Single, py As Single, oct As Long, depth As Long, slopeA As Single, slopeB As Single)
Dim mw As Long
mw = range ^ 2
Dim x As Single, y As Single

Select Case oct

Case 1:
      y = py - depth
      x = Int(px - slopeA * depth)

Do While GetSlopeStd(x, y, px, py) >= slopeB

If GetVisDistance(x, y, px, py) <= mw Then
    If room(x, y) = 1 Then
        If room(x - 1, y) = 0 Then RecursiveVisibility px, py, 1, depth + 1, slopeA, GetSlopeStd(x - 0.5, y + 0.5, px, py)
    Else
        If room(x - 1, y) = 1 Then slopeA = GetSlopeStd(x - 0.5, y - 0.5, px, py)
    End If
vismap(x, y) = 1
End If
x = x + 1
Loop
x = x - 1

End Select

If depth < range And room(x, y) = 0 Then
RecursiveVisibility startx, starty, oct, depth + 1, slopeA, slopeB
End If


End Sub
Are there any workarounds for these "blind spots" behind single obstructions?

Or, an even better question: Is this "flaw" important? How many roguelikes have been out there having these kind of issues and yet being fun as hell?

2

Programming / Re: Need help to implement a Line-of-Sight algorithm for a roguelike in VB6

« on: August 05, 2008, 02:31:38 PM »

Given the error data in my calculations, I fail to see how cut nodes will transform those values into something which resembles a true shadow cast behind an obstruction. And this data in my algorithm just don't work precisely even for a single obstruction.

For example, in my attachment, the blue node creates the 2 yellow nodes, which are both negative. If I cut the blue node, what do I gain?

Well, I'm disappointed. I'd better forget 1 year of work on my game and study some Quantum Mechanics for my exams. I suspect this is easier than any LOS algorithm.

3

Programming / Re: Need help to implement a Line-of-Sight algorithm for a roguelike in VB6

« on: August 04, 2008, 07:02:48 AM »

Well, during the weekend, I did some work with the algorithm in VB. Here are some images from what I've managed to do. The squares display the error data (ignore the 100's-it's the error data for an empty node with no obstruction data).




I didn't write any "cut nodes" code and any "obstruction data propagation stoppage" code. So, this far, is what is displayed by any means correct? What I did is the following:

1) Expand the perimeter.
2) For a given perimeter, check the obstruction nodes first and give data to adjacent nodes
3) Then expand the perimeter with the no-obstruction nodes.

NO node data overwriting occurs. When a node B is created from node A, only node A is responsible for giving data to node B, and no other node ever interferes with node B. This is why I am checking obstruction nodes first: If obstruction node at (3,3) can create 2 nodes with obstruction data at (2,3) and (3,4), the (2,3) node may already have been spawned by the "free" node of (2,4) first, and no obstruction data will be passed this way.

So for node (5,6) which is an obstruction, the obstructionX/obstructionY/error data is:

Node (5,6): (5,6) , error:0

And for node (4,6):

Node (4,6): (5,6) , error:-6

And for node (3,6):

Node (3,6): (5,6) , error:-12

And so on. So far, I don't see anything like "if a node's error data is ><=X then the node is obscure" which can be applied universally. For obstructions on the left/right side of the map, if the error is negative, then a shadow is SOMEWHAT correctly applied. THe same goes for obstructions on the upper/lower side of the map with positive error data. But I suspect this is not the way you did it, and surely isn't accurate as of now.

4

Programming / Re: Need help to implement a Line-of-Sight algorithm for a roguelike in VB6

« on: August 01, 2008, 11:12:07 AM »

@Birdofprey:

Great post! I will study your code (although I don't know sh** about C++). Also one remark about why this guy you're talking about used 2 coords for representing error data: In another forum/usenet/whatever he mentioned that error data could just as easily be an integer, positive or negative, just as you did, but he wanted his algorithm to be more "ready" for representing LOS in a 3D environment, hence the 2 coords (not that I actually understand why).

Anyway, back to my algorithm, after some more optimizations, i managed to make it really fast (30 repetitions in 120 milliseconds on a P2.4 GHz is quite good for a LOS of 20), but I discovered a severe inconsistency on what is seen ahead eg. in a narrow corridor:

If you notice what's happening on the far right wall at the end of the corridor,and the adjacent floor tiles, well...it's bad. So I guess I'm going for something else, like the method you used. I'll notify you for any problems I encounter 

5

Programming / Re: Need help to implement a Line-of-Sight algorithm for a roguelike in VB6

« on: July 31, 2008, 11:04:50 AM »

@ Brigand:

When you say that the algorithm hindered your performance, how many milliseconds it took to operate? With what sight range? On what system?

I managed to make a simple LOS program. On a P2.3 Ghz it takes a whopping 50 milliseconds to expand to a sight radius of ~20 in totally open space, and this time drops by a lot when many obstacles are placed around the entity (ie if the player is in a corridor)-say about 10 milliseconds.

I used a pre-computed line set (70 KB) which loads into an array, and also some *cough* *cough* graphic operations.

Jeez, in a map with 30 monsters it would take forever to LOS each and every one of them, so I'm probably taking your advice for the NPC's sight capabilities. That is, unless I figure out how the hell the algorithm in my first post works 

Here's the program (source and .exe) - 48 KB:

http://www.mediafire.com/?njgytjmtgkm

PS You think of yourself as being far from an expert, eh? What about taking a look at my code. Or taking a look at the code of every complete game I've written. I'm still trying to figure out why they work 

PS2 Oh and single obstructions aren't treated nicely in my program:

Not that I planned to use any single obstructions, though.

6

Programming / Need help to implement a Line-of-Sight algorithm for a roguelike in VB6

« on: July 30, 2008, 09:37:48 AM »

Greetings,

I am an amateur programmer from Greece who is currently trying to develop a roguelike resembling ADOM. I would like to implement an interesting algorithm that I found here:
http://www.geocities.com/temerra/los_rays.html
This is an algorithm about the Line of Sight (LOS) of the game entities, which means it calculates what an entity can and can't see (eg behind a column). It looks pretty fast and accurate, but alas it is poorly described in detail (especially towards the "end" of the algorithm) and the JAVA code link doesn't work any more.

I could really use some help, either with a piece of code with the above algorithm, or further explanation with steps on precisely what it does.

For those of you who have read the article: I actually understand what happens in diagrams a, b and c of the article, but I can't figure out how things evolve later, eg when and where a "pink obstruction" stops. Can it be when the x or y coord of the obstruction vector becomes less than zero? Anyway some VB code always helps!

Thank you in advance,
vdweller
http://vdweller.awardspace.com