I need some help. Ok my game has a grid, and I need my a character to make a straight line path from point A to point B, there are no obstacles to worry about. I have done this about 3 different ways and even invented 1 way of my own. But every way I try gives me the same results which is indeed ONE of he shortest paths possible, however it always gives me shortest path that I don’t want. Example: Here is a grid, the Red is the path it gives me, the Blue is the path I want. Both lines there are exactly 39 units long. Both are the shortest path, however as you can see the blue one is visually a straighter line then the red, and that’s what I need. Somebody please help! [Edited by - Kaanin on October 13, 2006 11:31:33 PM]

well, without seeing any code, my best guess is that it has to do with what value you're using to calculate the distance already traveled, at least if you're using A*. A* sorts by a value composed of an approximated distance still to go added to the actual distance already traveled [and sometimes some other stuff, like weights for turns, etc]. The distance traveled is obviously sqrt(dx*dx + dy*dy), but the pattern you're showing is gotten by adding '1' for each unit moved to the distance already traveled. This is fine if you restrict movement to horizontal and vertical, but a diagonal distance is actually sqrt(2) [roughly 1.414]. If you just use 1 for each step taken, then you get the shape you're describing, where diagonal steps are weighted with greater value than are horizontal/vertical steps.

Without seeing code, thats my best crack at your solution :P

Bresenham's line algorithm

ZOMG KrazeIke thank you SOO MUCH! This accursed thing has been plagueing me for days now. I could kiss you but Im guessing your a dude and I just dont swing that way. I just...wow, thank you so much.

This is kind of off-topic, but the title reminded me of a problem in Math that was open for many years. The problem is building a device that can draw a straight line. Using a ruler doesn't work, becuase you need to draw a straight line to make the ruler in the first place.

There's another way to get that straight line, too. I'm guessing that currently a diagnal move is equivilant to a straight move. However, if you make one diagnal move equivilant to 1.41 (the distance between the two centers of the squares) moves, it should find that the straight line is the shorter of the two and choose it (assuming that you have it choose the shortest possible path).

Quote: Original post by Ezbez
There's another way to get that straight line, too. I'm guessing that currently a diagnal move is equivilant to a straight move. However, if you make one diagnal move equivilant to 1.41 (the distance between the two centers of the squares) moves, it should find that the straight line is the shorter of the two and choose it (assuming that you have it choose the shortest possible path).

That won't work. The two paths in the diagram that Kaanin posted would have the same length under this definition of length as well.

Quote: Original post by alvaro
This is kind of off-topic, but the title reminded me of a problem in Math that was open for many years. The problem is building a device that can draw a straight line. Using a ruler doesn't work, becuase you need to draw a straight line to make the ruler in the first place.

How about using colored lead strings?

They have been used to draw straigth lines for centuries...

Quote: Original post by Steadtler

Quote: Original post by alvaro
This is kind of off-topic, but the title reminded me of a problem in Math that was open for many years. The problem is building a device that can draw a straight line. Using a ruler doesn't work, becuase you need to draw a straight line to make the ruler in the first place.

How about using colored lead strings?

They have been used to draw straigth lines for centuries...

I don't know exactly how the problem was stated, but I think it involved having a pen describe a line.

If the problem had been building a device that can draw a circle, the solution is as simple as an oblong block of wood with a nail on one end and an attached pen at the other. You place the nail at some fixed point in the plane and, as you rotate the tool, the pen will describe a circle.

For drawing a line, the solution I know uses seven oblong blocks of wood of various lengths.

<off-topic>

alvaro and Ezbez, do you have a link to this problem and the solution? It sounds fascinating.

</off-topic>