how to simulate line with pset.

[Agamemnus]

edit: gotta love reusable posts. See bottom for my other question.

This used to be a different thread:
the standard algorithm to determine paths on a map (for a unit to move in an RTS, for instance) is A*. However, A*requires a graph of points and lines. Each line says how much work it takes to traverse it.

I am not exactly sure how A* works, but my algorithm will traverse all the paths. It will choose the first solution that it gets to. Then it will optimize that path. It will check other solutions by swapping endpoints....

Code:

|          |
\          |
/          |
|          |
path 1 / 2

Ok. So, the problem is this:
To make a graph, I first find the border of each landmass and then I find the unique contiguous borders from the one big border, as this picture illustrates:
[img] http://www.geocities.com/pisforpi/weird2.bmp [/img]
(you'll have to do Save As, or go to the main page and THEN go to the image..silly geocities!)
I need to separate this even further by separating individual segments. The solution to this is to remove extraneous points on any border and then see whether any point on a border touches two other points. If it doesn't, separate it.

But I can't figure out how to remove the extraneous points.

Help! :???:

[pr0gger]

<-- is very glad right now that he is not doing pathfinding

<--finds a link, hopes it helps

http://rajiv.macnn.com/tut/search.html (search the page for A-Star, near the bottom)

[Agamemnus]

I still need the graph!!

Another source says that you should start from the graph and then make the terrain. But this makes it really hard to make good authentic terrain.

[pr0gger]

interesting....

i can think of another way, but it is not as useful... hmmm...

[Agamemnus]

--------------------

Edit: (3rd time)

Line/border search>>

Code:

line(a, b)
system

sub line (x1, y1, x2, y2)
dim x.temp as integer, y.temp as integer
do
add to x.temp and y.temp accordingly and in steps (|__)
path.x = x.temp
if map(x1,y1) = blocked then
if NOT already.followed(x.temp, y.temp, 1) then follow.border (x.temp, y.temp, z, 1)
NOT already.followed(x.temp, y.temp, -1) then follow.border (x.temp, y.temp, z, -1)
end if
if x.temp = x2 then
if y.temp = y2 then
exit sub
end if
end if
loop
end sub

sub follow.border (border.index, sign)
do
add to x.temp and y.temp according to border and sign
if vertical or horizontal in direction of x2, y2 possible then
if touch(line) <> border.index then
line(x.temp, y.temp,x2,y2)
end if
exit sub
elseif border.forks then
if NOT already.followed(x.temp, y.temp, 1) then follow.border (x.temp, y.temp, z, 1)
NOT already.followed(x.temp, y.temp, -1) then follow.border (x.temp, y.temp, z, -1)
end if
loop
end sub

Or something. But I still need to make the damn border graph.

[Neo]

:???: Er... I still don't really understand how and what you are doing.

But I do have a suggestion, which is why can't you use any numerical or shaple Vertexes?

[Agamemnus]

numewhat? :???:

Ok, so here is the problem:
I want my unit to go zig-zag from one point to another. (simulating a line) Problem is, the unit can only go up and down. The code so far is a bit iffy. I want to spread out the extra case where my line pattern ends:

Code:

DIM SHARED x.s AS INTEGER, y.s AS INTEGER, x1 AS INTEGER, y1 AS INTEGER
DIM SHARED x2 AS INTEGER, y2 AS INTEGER, x3 AS INTEGER, y3 AS INTEGER
DIM SHARED z AS INTEGER, z2 AS INTEGER, z3 AS INTEGER, z4 AS INTEGER
x1 = 45: y1 = 95
x.s = 0: y.s = 0
x4 = x.s + x1
y4 = y.s + y1
RANDOMIZE TIMER: SCREEN 13
z2 = 0: z3 = ABS(x1) + ABS(y1): x2 = x.s: y2 = y.s
IF x1 > y1 THEN x3 = 1: y3 = x1 / y1: GOTO t1
IF x1 < y1 THEN y3 = 1: x3 = y1 / x1: GOTO t1
IF x1 = y1 THEN y3 = 1: x3 = 1: GOTO t1
t1: DO
z2 = z2 + 1: z4 = z4 + 1
IF z = 1 THEN x2 = x2 + 1 ELSE y2 = y2 + 1
IF (z4 >= y3 AND z = 1) OR (z4 >= x3 AND z = 0) THEN z = 1 - z: z4 = 0
IF x2 = x4 THEN z4 = z4 - 1: z = 0 ELSE IF y2 = y4 THEN z4 = z4 - 1: z = 1
PSET (x2, y2)
LOOP UNTIL INKEY$ <> "" OR (x2 = x4 AND y2 = y4) OR z2 = z3
PSET (x.s, y.s), 7
PSET (x.s + x1, y.s + y1), 7

[wizardlife]

I'm too lazy to look at all your code... but I will tell you the general principle of how to trace a straight diagonal line between two points. (and thus how to make your unit go diagonally from points A to B on a cartesian plane)

starting point = (x1, y1)
destination = (x2, y2)

First determine the x and y differences (how far it has to travel North-South or East-West):

Code:

xdif = x2 - x1
ydif = y2 - y1

Next, decide which of those is greater and base your line algo around that one:

Code:

IF xdif > ydif THEN
  FOR ctr = x1 to x2
  NEXT
ELSE
  FOR ctr = y1 TO y2
  NEXT
ENDIF

Now within each loop, scan across the 'long' plane and plot a point on the short plane based on the percentage of the long plane used up... if that makes any sense.


The way I'd do it in the context of an RTS, however, is simply check what the differences are and move one square in the axis direction of the greater difference...

[Agamemnus]

that's just your basic line for my still-unfinished pathfinder, though. But I did all you said. That isn't really the problem. The problem is when the bigger one does not divide the smaller one evenly.

[relsoft]

Try normalizing:

Note all vars should be singles...


DX=x2-x1
dy=y2-y1

L!=sqr(DX*dx+dy*dy)

NX!=DX/L!
NY!=dy/L!


For I=0 to L!

X1=x1+NX!
Y1=Y1+NY!
Pset(x1!,Y1!),15
Next I