Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - calculating grid cells in move between cells

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    8

    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 ..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    8
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2011
    Posts
    8
    yes, I would say you can move like a knight or in any basic direction ..
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2011
    Posts
    8
    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 ..
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jan 2011
    Posts
    8
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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:

    calculating grid cells in move between cells-calculating-grid-cells.jpg

    C3, D3, D4, E4, E5, F5, G5, G6, H6, H7, I7, J7, J8, K8, K9, and L9. Is that correct?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jan 2011
    Posts
    8
    yea, that seems to be what I am looking for.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Jan 2011
    Posts
    8
    thanks, yea I have been doing programming for a long time, but my math skills are kind of rusty
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Jan 2011
    Posts
    8
    thanks a bunch ..

    I'm tempted to go with the easiest solution
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: February 9th 2010, 01:03 AM
  2. Dirichlet cells construction
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: May 17th 2009, 10:21 AM
  3. Replies: 4
    Last Post: May 7th 2009, 10:47 AM
  4. Referencing matrix cells in matlab
    Posted in the Math Software Forum
    Replies: 1
    Last Post: March 25th 2009, 03:45 PM
  5. Internal Resistance and Solar Cells
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 22nd 2009, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum