Retroactive journal entry

Pig on 2009/09/01 18:47 of self is None
— edited on 2009/09/01 18:52

Day 3 part 1

-Retroactively updated journal

-Added screenshot.

Day 2

-Too many other things to do. Really shouldn't be working on this.

-Experimented with pygame.mixer

Seems to work ok.
Still need to find sounds that's not just those on the hard disk. Although they do come from open source programs.
Also have to find something to use for the main sprite (this should really be a priority).

-Added some story element triggers.

-Spent yet another hour on the line segment intersection algorithm...

Day 1

-Completed basic mechanics

-Spend 1-2 hours on determining if two line segment intersect(!)

Shouldn't there be some well known numerically stable algorithm or a module?

-Other things seem to be taking less resources than expected.

-This is nowhere near done and there is not much time left.

Originally, only 1 day was planned...

(log in to comment)

Comments

Tee on 2009/09/01 19:34:

About finding an intersection between two segments, I'm not sure if you're already using this (if you are, sorry for being superfluous, but just in case), given points x = (x0, x1), y, z, remember that the determinant of the matrix ((x0, x1, 1), (y0, y1, 1), (z0, z1, 1)) gives you the twice the area of xyz triangle in counterclockwise direction. Which means, if that's positive, then z is to the left of the xy segment, and if it's negative, then z is to the right (if it's zero, then it's collinear). With this, it should be straightforward to calculate intersection, just check if each point of a segment are in opposite sides of the other segment (do it for both of them).

(I think the determinant can be simplified to (y1 - x1)*(z2 - x2) - (z1 - x1)*(y2 - x2) -- or something like that, not sure if this is right.)

(Ok, now I should stop reading posts and lurking on IRC and start working on my game...)

Pig on 2009/09/01 22:42:

Thanks for posting. Yes, I was already using a counter-clockwise test by the end of Day 1. However, the problem arises when all points are (nearly) collinear. Since, I'm using doubles for my coordinates (int would have probably been a much better choice), I can't test if I'm getting exactly 0. I'm worried about testing to see if the absolute value is less than epsilon since (I think) it could also mean that the line segments (and thus the area of the triangles) are small without actually having them collinear.

The other thing is that I'm not quite sure what to do in the collinear case. I'm currently using a coordinate-wise "inbetween" test (check if one endpoint of line1 is between the endpoints of line2). But I'm running this test along with the counter-clockwise time whenever the lines' direction vectors are (near) parallel (by taking the dot product). But again, I'm not sure if what I'm doing is numerically stable (especially with short line segments)

Tee on 2009/09/02 00:54:

Well, I don't know how small your segments are, but I would guess that it's possible to find an epsilon big enough to account for stability and small enough to avoid any other problems... I mean, I don't see where you'd lose too much precision. If it really is a problem, maybe you might want to consider scaling. But I'm not sure either, it depends on the case, but I think that in the general case, numerical stability shouldn't be much of a problem.

Pig on 2009/09/02 11:57:

I think you are right. I can bound the length of the segments from below and then I just need to pick the threshold on the height of the triangle for collinearity.