# Determining travel along a line on a grid

Page 1 of 1

## 8 Replies - 2110 Views - Last Post: 13 January 2011 - 09:20 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=209448&amp;s=b099ed72afab44e2315e0ea74e779f80&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 rjolitz

Reputation: 7
• Posts: 111
• Joined: 17-May 08

# Determining travel along a line on a grid

Posted 11 January 2011 - 07:35 PM

Hi All.

I'm working on a BBG that uses X,Y coordinates for positions. What I've been trying to search out is a formula to determine:

You are point A [1,1]

You wish to travel to point B [100,100]

The distance is ~140.

You have 20 points to use for movement. Where is the X,Y coordinate you can reach?

I've not been able to figure out the formula that will determine that. Can anyone point me in the right direction to try to puzzle this out? I have the formula for determining distance between the 2 target points.

Clear as mud?

Thanks...

Is This A Good Question/Topic? 0

## Replies To: Determining travel along a line on a grid

### #2 Kilorn

• XNArchitect

Reputation: 1361
• Posts: 3,534
• Joined: 03-May 10

## Re: Determining travel along a line on a grid

Posted 11 January 2011 - 07:42 PM

Well, you've stated that you want to move from [1,1] to [100,100]. You should already know how many points along that line an object can be in, unless you're allowing the objects to stop between points, e.g. [1.2, 4.6]. If an object has 20 points to use for movement, and if the object uses 1 of these "points" each time they move to a new point along the line, then it would be easy to figure out how many places the object has moved along that line using simple math. [1,1] + 20 movement points spent = [21, 21]. Assuming you're doing movement in that way. Unless you're making x and y movements independent of each other, in which case, [21, 1], [1, 21], or [11, 11] would be the theoretical limits of movement combinations while using 20 points to move. If I'm way off on what you were expecting, let me know and maybe I can explain a little better what I meant by all of this jibberish.

### #3 rjolitz

Reputation: 7
• Posts: 111
• Joined: 17-May 08

## Re: Determining travel along a line on a grid

Posted 12 January 2011 - 09:46 AM

Kilorn, on 11 January 2011 - 08:42 PM, said:

Well, you've stated that you want to move from [1,1] to [100,100]. You should already know how many points along that line an object can be in, unless you're allowing the objects to stop between points, e.g. [1.2, 4.6]. If an object has 20 points to use for movement, and if the object uses 1 of these "points" each time they move to a new point along the line, then it would be easy to figure out how many places the object has moved along that line using simple math. [1,1] + 20 movement points spent = [21, 21]. Assuming you're doing movement in that way. Unless you're making x and y movements independent of each other, in which case, [21, 1], [1, 21], or [11, 11] would be the theoretical limits of movement combinations while using 20 points to move. If I'm way off on what you were expecting, let me know and maybe I can explain a little better what I meant by all of this jibberish.

I think we are close.

1 point does not equal 1 movement on the X axis or 1 movement on the Y axis. It is possible to travel to 3,3 which would be I think 2 movement points.

the goal is if your target coordinate is a further distance then available movement points, how far can you get.

Or am I over complicating the process when 1 change in either axis = 1 point of movement?

Opinions?

### #4 anonymous26

• D.I.C Lover

Reputation: 2
• Posts: 3,638
• Joined: 26-November 10

## Re: Determining travel along a line on a grid

Posted 12 January 2011 - 01:13 PM

What's a valid move? Can you move to diagonal grid element, or must they all be adjacent?

### #5 Kilorn

• XNArchitect

Reputation: 1361
• Posts: 3,534
• Joined: 03-May 10

## Re: Determining travel along a line on a grid

Posted 12 January 2011 - 01:16 PM

Good question, . Are we allowed to use 1 movement point to increase our position from [1,1] to [2,2] or would that be two movement points to go from [1,1] to [2,1] to [2,2]?

### #6 Fib

Reputation: 163
• Posts: 554
• Joined: 12-March 09

## Re: Determining travel along a line on a grid

Posted 12 January 2011 - 07:30 PM

rjolitz, on 11 January 2011 - 07:35 PM, said:

... I'm working on a BBG ...

I may be able to help, but first off, what is a BBG?

This post has been edited by Fib: 12 January 2011 - 07:30 PM

### #7 anonymous26

• D.I.C Lover

Reputation: 2
• Posts: 3,638
• Joined: 26-November 10

## Re: Determining travel along a line on a grid

Posted 12 January 2011 - 10:11 PM

Fib, on 13 January 2011 - 01:30 AM, said:

rjolitz, on 11 January 2011 - 07:35 PM, said:

... I'm working on a BBG ...

I may be able to help, but first off, what is a BBG?

I guess it's 'Browser Based Game'.

### #8 alexzar

Reputation: 0
• Posts: 2
• Joined: 09-January 11

## Re: Determining travel along a line on a grid

Posted 12 January 2011 - 10:54 PM

If you are talking "as the crow flies" just going from point A to point B the formula is:

sqrt((fromX - toX)2+(fromY - toY)2)

That gives you the distance of a direct line between those points. What you do with that number from there is all up to you. You also might want to round the distance number to make it easier to work with.

If you are talking about determining movement costs along a grid, and 'walking' from point a to point b, you want to look into a* pathfinding. There are dozens of websites out there that get into detail on that. In that case, Google is your friend.

This post has been edited by alexzar: 12 January 2011 - 10:58 PM

### #9 Fib

Reputation: 163
• Posts: 554
• Joined: 12-March 09

## Re: Determining travel along a line on a grid

Posted 13 January 2011 - 09:20 AM

Well, if you mean what I think that you mean, then you really don't need a "formula."

Use grid based movement to determine when movement points should be removed. If the "player" is sitting in the cell [1, 1] of your grid, and they request to move to [1, 2] of your grid, remove one movement point. If the player requests to move, but has zero movement points, then do not allow the movement.