# Thread: calculating grid cells in move between cells

1. ## calculating grid cells in move between cells

What is the basic calculation or formula to calculate what cells are passed through in a 2 dimensional checkerboard like grid in a move between cells ?

Say I am at x1,y2 and I want to move to x2,y2. I want to calculate all the cell coordinates I have to pass through in that move. Sorry if my math is a bit rusty, but offhand I am not sure what the formula is ..

2. I'm assuming you're in Excel or some sort of spreadsheet. The answer is going to depend greatly on the path you take. Are you allowed to move diagonally? Or must you always move only in either a horizontal or vertical fashion?

3. It's a programming problem in the ruby programming language I am working on. I am using a 2 dimensional custom object as a 2 dimensional array to represent the grid .. yes, diagonal moves are allowed

4. What kind of diagonal moves are allowed? If I increase x by 1, can I only increase y by 1? Or could I increase 2 in y for only 1 in x? If I think about a chessboard, then my question is this: are diagonal moves only allowed as per the way a bishop moves? Or could you move the way a knight does?

5. yes, I would say you can move like a knight or in any basic direction ..

6. So how are you defining what "cells are passed through"? If I go from (1,2) to (2,2), then I've traveled from one cell to an adjacent cell. If I go from (1,1) to (2,2), then, depending on how you define "cells passed through", I might have again just traversed from one cell to an adjacent cell, so a distance of 1; or, if I have to measure the diagonal distance in a sort of euclidean way, I'd have gone through $\sqrt{2}$ cells; finally, I might have to measure in a "taxicab" fashion, in which case I actually have to traverse like this: (1,1) -> (1,2) -> (2,2), in which case I'd have gone a distance of 2 cells.

So the question is this: how are you measuring distance here?

7. It's just this game thing that I am supposed to partially implement where it says a player can shoot from any space towards a destination space but the projectile may hit objects in other spaces such as trees before it gets there on the way .. It is not limited by how far away the target space may be ..

8. Ah. So the grid is a 2D representation of actual physical space? If that's the case, then you want your Euclidean distance formula, I would think. That is, in moving from $(x_{1},y_{1})$ to $(x_{2},y_{2}),$ the distance traversed is equal to

$\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}.$

That's just the Pythagorean theorem, really. Make sense?

9. I have a ruby function to calculate the distance, but I need to figure out the coordinate of every cell in between the starting and ending cell

10. Ok. So, just to be perfectly clear, as an example, you're asking for a function to return the coordinates of all the green cells in the attached file, right? That is, given a move from C3 to L9, you want to be able to return the following list:

C3, D3, D4, E4, E5, F5, G5, G6, H6, H7, I7, J7, J8, K8, K9, and L9. Is that correct?

11. yea, that seems to be what I am looking for.

12. Hmm. There are some subtleties here that are eluding me. I could probably solve this problem if I thought long enough about it, but it's probably better for you and me if I invite a better programmer to make sense of this problem. I think undefined (an MHF user) might be able to do well here.

Cheers.

13. thanks, yea I have been doing programming for a long time, but my math skills are kind of rusty

14. Hi, thanks for the kind words, Ackbeet.

I haven't programmed in Ruby but know some basic syntax. I found a nice discussion on line drawing algorithms here, with examples given in Java (caution: contains applets, which on my computer causes Firefox to freeze for a second or so):

Line-Drawing Algorithms

I'm wondering about your preference between these lines and Ackbeet's attachment in post #10. Note that the "prettiest" line might not necessarily be the most suitable model for hit detection. I would like you to state a preference, since I've never worked with hit detection before and don't know what choice is most "natural". If the project is important to you, you might want to do an internet search on hit detection to see what is commonly done.

Also it's worth clarifying whether you really want a list of all intermediate cells, or simply a boolean function that will tell you whether a particular cell (or group of cells) is in the path of your projectile.

Hope this seems reasonable to you. I can get more into specifics when more details are provided.

15. thanks a bunch ..

I'm tempted to go with the easiest solution

Page 1 of 2 12 Last