4 Replies - 305 Views - Last Post: 29 June 2013 - 01:43 PM Rate Topic: -----

#1 grimpirate  Icon User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 714
  • Joined: 03-August 06

Lookup Table?

Posted 27 June 2013 - 07:49 PM

I've been working on a puzzle game recently (it can be found in the Share Your Project forum under Battleship Solitaire). The puzzles themselves involve tiled components. My approach was to treat the entire game "board" as a one-dimensional array. As a for instance, if the puzzle is 3 x 3 I create a one-dimensional array of 9 Tile objects. However, for the purposes of updating the board in certain ways I need to consider the actual puzzle itself as a 5 x 5 puzzle (or a 25 length array). Finally, for the purposes of updating the board graphically (i.e. its view) I need to consider a 4 x 4 space (or a 16 length array). I call these different arrays array space, puzzle space, and tiling space, respectively. Wherein I need to do a conversion in order to retrieve the tile objects from the array space dependent on the current operation being performed.

To approach conversion from one space to another space (much as in a change of basis in linear algebra) there are simple arithmetic conversions. I noticed that rather than performing the array offset conversions mathematically I could use a lookup table. That's confusing, so allow me to show each array's contents (for a hypothetical 3 x 3 puzzle):

object array
[Tile  0][Tile  1][Tile  2]
[Tile  3][Tile  4][Tile  5]
[Tile  6][Tile  7][Tile  8]


puzzle array (puzzle space to array space)
[-1][-1][-1][-1][-1]
[-1][ 0][ 1][ 2][-1]
[-1][ 3][ 4][ 5][-1]
[-1][ 6][ 7][ 8][-1]
[-1][-1][-1][-1][-1]


tiling array (tiling space to puzzle space)
[ 6][ 7][ 8][ 9]
[11][12][13][14]
[15][16][17][18]
[21][22][23][24]


This may all seem very convoluted, but there are reasons for it: modularity, ease of code readability, and the checks that are performed for valid inputs into the puzzle.

After this lengthy exposition the question boils down to this, what are the situations where a lookup table might be preferrable to "on the fly" calculations. Are they always preferrable? Are there other approaches?

This post has been edited by grimpirate: 27 June 2013 - 07:50 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Lookup Table?

#2 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 1
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Lookup Table?

Posted 28 June 2013 - 02:05 PM

Rather than a look-up table I would have been inclined to have some kind of hierarchical structure, commonly known as a 'tree'. That way your object array's nodes can have leaves that represent locations on your puzzle array for instance. You should find it's more efficient than a look-up table, or set of them.
Was This Post Helpful? 0
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Lookup Table?

Posted 28 June 2013 - 04:34 PM

Are you using a language that only lets you put ints in the array? Couldn't you just put a pointer/reference to the tiles in the arrays? That way, instead of lookup arrays, you have materialised views.
Was This Post Helpful? 0
  • +
  • -

#4 grimpirate  Icon User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 714
  • Joined: 03-August 06

Re: Lookup Table?

Posted 29 June 2013 - 12:57 PM

@ButchDean: I followed none of that. From my limited computer science knowledge I understand trees/nodes to be an advanced topic. That's why my question was about lookup tables and arithmetic conversions as opposed to anything else.

@cfoley: It's coded in Java, and I think I may have originally been doing that but suffered some sort of performance loss. I'll have to take a look at my code again and see why I opted to use the integer arrays. I recall that originally each Tile object had a getPosition method, and what you're saying makes a lot of sense. However, I think computation-time wise I reasoned that looking in an array for an integer offset would consume less time than calling Tile.getPosition(). I recognize of course that these are inferences I'm making and could be way off the mark.
Was This Post Helpful? 0
  • +
  • -

#5 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Lookup Table?

Posted 29 June 2013 - 01:43 PM

In a 5x5 grid it will be fast no matter what you do. Instead of an array if int, use an array of Tile.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1