Algorithm help (off topic?)

SDL Development
1

I need help with an algorithm I’m writing in a game. I’m using SDL to write the game, although this algorithm really has nothing to do with SDL, but I thought it would be a shame not to tap into the knowledge on this list.

I’m creating a game that has the character moving around the screen (only horizontally and vertically), creating a line behind them (it’s a clone of the touch screen game you see at taverns, with the eyes). My problem is determining when the player draws a rectangle. Right now I have a linked list of all the points that the player has passed over (I’m not even sure if that’s the best way to do this).

I was thinking that when the player insersected a previously drawn line, I could check a point on both sides of the “T” to see if it is in a rectangle. However, I have no idea how to do this.

Is there a tutorial/discussion anywhere on this sort of thing?

Any other ideas on how to accomplish this?

Should I post this problem somewhere else?

2

There are a few ways to o about this…

You say that you’re storing a linked list of points? That seems like a
lot of data, most of which you don’t need… I might try storing a
list of line segments. Split a line segment every time you cross it.
Each line segment data structure should have a pointer to the six other
line segments which share a point with this line segment.

#1####2#
3±—+4
#5####6#

Then when you want to check if there is a rectangle involving a certain
corner (i.e., the point where you just crossed another line) then you
can do a recursive function on that graph for three turns that get you
back to where you started.

Just a first idea… don’t know if it’s good to implement or not.

Good luck,
Ben.On Fri, 2002-10-25 at 12:07, Buck Lemke wrote:

I need help with an algorithm I’m writing in a game. I’m using SDL to write the game, although this algorithm really has nothing to do with SDL, but I thought it would be a shame not to tap into the knowledge on this list.

I’m creating a game that has the character moving around the screen (only horizontally and vertically), creating a line behind them (it’s a clone of the touch screen game you see at taverns, with the eyes). My problem is determining when the player draws a rectangle. Right now I have a linked list of all the points that the player has passed over (I’m not even sure if that’s the best way to do this).

I was thinking that when the player insersected a previously drawn line, I could check a point on both sides of the “T” to see if it is in a rectangle. However, I have no idea how to do this.

Is there a tutorial/discussion anywhere on this sort of thing?

Any other ideas on how to accomplish this?

Should I post this problem somewhere else?

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
–
…
: Benjamin Keil : If she’s a liar, I’m her lover :
: Graduate Student in : If she’s a priestess, I’m her cover :
: Linguistics and as : If she’s a lady, I’m her man :
: Poor as that sounds : If she’s a man, I’ll do what I can! :
:…:… Alphaville, from Jet Set Society …:

3

this is a small optomization but check it out…

for a rectangle you dont need to store 4 points, you only need to store 2.
You can either Store the corner points of a rectangle and reproduce it that
way…(store A and B from below)

A------
| |
-------B

or you can store A and the size of the triangle in X and Y. That way if A
is (3,5) and B is (4,6) you can store A (3,5) and store the second point as
(1,1) which is the size of the triangle and just do addition where
appropriate to get the other corners.

I hope this helps atleast a small amount.

-Atrix> ----- Original Message -----

From: bkeil@ucla.edu (Benjmain Keil)
To: “SDL Developers list”
Sent: Friday, October 25, 2002 6:36 PM
Subject: Re: [SDL] Algorithm help (off topic?)

There are a few ways to o about this…

You say that you’re storing a linked list of points? That seems like a
lot of data, most of which you don’t need… I might try storing a
list of line segments. Split a line segment every time you cross it.
Each line segment data structure should have a pointer to the six other
line segments which share a point with this line segment.

#1####2#
3±—+4
#5####6#

Then when you want to check if there is a rectangle involving a certain
corner (i.e., the point where you just crossed another line) then you
can do a recursive function on that graph for three turns that get you
back to where you started.

Just a first idea… don’t know if it’s good to implement or not.

Good luck,
Ben.

On Fri, 2002-10-25 at 12:07, Buck Lemke wrote:

I need help with an algorithm I’m writing in a game. I’m using SDL to
write the game, although this algorithm really has nothing to do with SDL,
but I thought it would be a shame not to tap into the knowledge on this
list.

I’m creating a game that has the character moving around the screen
(only horizontally and vertically), creating a line behind them (it’s a
clone of the touch screen game you see at taverns, with the eyes). My
problem is determining when the player draws a rectangle. Right now I have
a linked list of all the points that the player has passed over (I’m not
even sure if that’s the best way to do this).

I was thinking that when the player insersected a previously drawn line,
I could check a point on both sides of the “T” to see if it is in a
rectangle. However, I have no idea how to do this.

Is there a tutorial/discussion anywhere on this sort of thing?

Any other ideas on how to accomplish this?

Should I post this problem somewhere else?

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
–
…
: Benjamin Keil : If she’s a liar, I’m her lover :
: Graduate Student in : If she’s a priestess, I’m her cover :
: Linguistics and as : If she’s a lady, I’m her man :
: Poor as that sounds : If she’s a man, I’ll do what I can! :
:…:… Alphaville, from Jet Set Society …:

SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl