hiii

imagine your self you have a hexagon board fill up with hexagons

now, the ball can only move from one place to another if he has an "open way"

"open way" - an empty hexagon(s)

for example if the user wants to move tha ball from 0 to 32 he needs free hexagons to get there

x-10 x-9
x-1 x x+1
x+9 x+10

oh, the ball has 6 directions that it can move

note in the picture blow , the numbers on the board
so for example cell between 4 to 9 . doesnt exist , or better they do exist but not in use at this moment

i need help . i tried to think on this several days.. but i cant find any solution to my problem .. any ideas?

thanks

eko

Posted on 2002-09-13 19:47:01 by eko
First, I can not see your image. Second, I'm not sure of the question, but if your just want to know a possible way to address the grid then I would use the method below. See the colored numbers? The hexagon grid is seen as two arrays (you can combine them in your code, but we are just brain storming here) - one yellow, one white. Knowing if there is an open space is simply a matter of checking the two arrays.
Posted on 2002-09-13 22:40:16 by bitRAKE
any ideas?

thanks

eko
Posted on 2002-09-14 11:43:03 by eko
You could store an array of valid ranges like this:
``````
ranges db 0,4,9,14,18,24,27,34,36,44.... ; 0-4, 9-14, 18-24 etc
``````

Just calculate the position as if you had an infinite board, then check if the result fits into one of the ranges..

Thomas
Posted on 2002-09-14 13:35:33 by Thomas
i can calculete this range ... this is not my problem
my problem . is how to get the way

the ball has 6 directions to "walk" throw
and if i need to go from 0 to 37 or thing like that .
i need to make up an algo to check if the way is free
Posted on 2002-09-14 13:45:10 by eko
You mean like solving a maze puzzle?

You could make a big tree of possible moves (recursively), and find out if one of the paths reaches the destination. There are good algorithms for optimizing the tree search (http://www.generation5.org/simple_search.shtml, http://www.generation5.org/astar.shtml)

Thomas
Posted on 2002-09-14 13:52:16 by Thomas
exactly like solving a mze puzzle one the problem I need to fit it to my board and that each ball can move to 6 directions

any ideas?
Posted on 2002-09-14 14:02:48 by eko
if i do trees search . does it check the all posibilities?
Posted on 2002-09-14 14:14:51 by eko
eko,

Since you said you can determine the range. (I'm not sure if I understood the problem but here's my try.)

Intro:You might want to save the image below while you are reading the content of this thread.

1. Create an array of 80 bytes.
2. Initializing all 80 bytes to 0.
3. Mark the walls(not free cells) for example 10, 20 and 30 as 1
4. We all know that by going left from current position the number decreases by 1 and going right increases the current position by 1.

5. If we go NW or SE from the current position, the cell difference is 10.

E.G. 11 going to 21 the difference is |10| {|x| absolute value}

How do we determine if the ball is moving NW or SE:

NW: the starting position is greater than the ending position
SE: the starting position is less than the ending position

6. If we go NE or SW from the current position, the cell difference is 9.

E.G. 11 going to 20 the difference is 9

How do we determine if the ball is moving NE or SW:

NE: the starting position is greater than the ending position
SW: the starting position is less than the ending position

You can derived from the differences if the ball's movement is valid or not.

Look at the sample image below. We start at 21.

1. If we go left subtract 1 we get 20 then check if array 20 is equal to 1, if 1 then it's a "wall" or "not free"
2. going right adds 1 to the current position...
3. Going TO 1 FROM 21. Since the starting position is greater than the ending position we know it's going north but we don't know if its either NE or NW. (see above condition)

We can see in our eyes it's going NW but algorithmically we don't know the solution.

Solution:

first we know that going NW the difference of cells is 10 and going NE the difference of cells is 9. (see above condition)

checking if ball is going NE

If we subtract 21 by 9 we get 12
continue to subtract that by 9 we get 3 (continue this step until a match of the ending position is found or the difference is a negative value)

is 3 == 1? no, so NE isn't the direction of the ball

checking if ball is going NW

If we subtract 21 by 10 we get 11
continue to subtract that by 10 we get 1 (continue this step until a match of the ending position is found or the difference is a negative value)

is 1 == 1? yes, so NW is the direction of the ball

the value 1 we are checking is the ending position and the current difference of cells. Here we conclude that this is a valid move.

if any checking of the values doesn't match, then the move is invalid. for example going TO 10 FROM 21 there is no way on the subtraction process you'll ever get a difference of 10 on both checks(NW and NE directions)

Now checking for exceeding a "wall"...

if you take a look at the picture below, you can see we start at cell 21. for example we go to cell 18. We can see that there is a block or "wall" on 20. To check this ambiguity. All you have to do is determine the start the by adding or subtracting from the current position until you arrived at the ending position while checking if the array has a flag of 1.

E.G.

from 21 going to 18.

1. 21 - 1 == 20 check array[20] if it's set to 1 if it's not, decrease further

2. Since 20 is set to 1 then the move is invalid...

It's complicated than first thought. I hope you understood what I've said. As long as you follow the rules I set above, I'm sure you can solve the problem.

The lines below shows the possible movements.

P.S. as for determining whether going E or W, this condition happens when the check for NW and NE or SE or SW doesn't conclude any match of the ending position.

I have not tested this on a program, there might be errors on something I've said... :) forgive me if there are errors or have not understood the problem. :grin:
Posted on 2002-09-14 15:25:22 by stryker
Eko, here's a solution I thought up, but note it only works with your hexagon dimensions. I apologize for using pseudo-C code but I think ASM would make the post too large.

First create a 61x4 byte table cell array to store x,y,z,_ info for each hexagon cell.

Pseudo-C code:
``````[size=12]typedef struct {
char x;
char y;
char z;
} XYZ;

XYZ cell_table[61];

int XYZtoCellIndex( char x, char y, char z )
{
return ( z > 4-y )
? (-(y*y)-(z*z)-(2*y*z)+(25*y)+(27*z)+(2*x)-32) >> 1
: ((y*y)+(z*z)+(2*y*z)+(9*y)+(11*z)+(2*x)) >> 1;
}

XYZ CellIndexToXYZ( int c )
{
XYZ t;
t.x = cell_table[c].x;
t.y = cell_table[c].y;
t.z = cell_table[c].z;
return t;
}

void GenerateTable( void )
{
int x, y, z, c;
ZeroMemory( cell_table, 61*4 );
for( z=0; z<5; z++ ){
for( y=0; y<5; y++ ){
for( x=0; x<5; x++ ){
c = XYZtoCellIndex(x,y,z);
cell_table[c].x = x;
cell_table[c].y = y;
cell_table[c].z = z;
}}}
}[/size]``````

Then you'll probably want a 61 byte array to hold board/player/piece data.
After that, moving pieces around is as simple as checking x, y, z.

``````[size=12]bool isPathClear_X( int cell, int relative_x )
{
int i;
int c, bd;
XYZ t = CellIndexToXYZ( cell );

if ((t.x + relative_x) < 0) || ((t.x + relative_x) > 4)
return false;

for( i=1; i <= abs(relative_x); i++ )
{
c = XYZtoCellIndex((relative_x<0)?t.x-i:t.x+i,t.y,t.z);
if( board_data[c] & FLAG_OCCUPIED )
return false;
}

return true;
}

bool isPathClear_Y( int cell, int relative_y );
bool isPathClear_Z( int cell, int relative_z );[/size]``````

I hope you understood that. I included a diagram to help visualize.
Posted on 2002-09-14 19:38:59 by iblis
Now that I look at it, you could just use the .padding element of the xyz struct to hold board data.
Posted on 2002-09-14 19:55:41 by iblis
hiii
thanks for the ideas.. if some of you have more ideas. please continue give them.

iblis:can you explain alittle how does it work ?

and what is : and ?

i thought on my own idea . it doesnt work . maybe you can help me fix it

i have array of all the free spaces in the board

so i thought maybe i'lll do Recorsiv to check the way . but it doesnt work .. i have mistake and icant find it

``````

RecorsivCanWalk proc ;cell:BYTE

;cmp found,1
;je @finish
mov bl,byte ptr [esp+4] ;save alot of push ebp pop ebx . stack size
cmp bl,towhere
je @finish
cmp bl,fromwhere
jne @F
mov found,2
jmp @didntfind
@@:
invoke IsItThere
jc @didntfind
mov ebx,[esp+4];cell

push ebx
call RecorsivCanWalk

cmp found,0
jnz @finish
;invoke RecorsivCanWalk,bl
mov ebx,[esp+4];cell
dec bl
push ebx
call RecorsivCanWalk
cmp found,0
jnz @finish

;invoke RecorsivCanWalk,bl
mov ebx,[esp+4];cell
sub bl,10
push ebx
call RecorsivCanWalk

cmp found,0
jnz @finish

;invoke RecorsivCanWalk,bl
mov ebx,[esp+4];cell
sub bl,9
push ebx
call RecorsivCanWalk

cmp found,0
jnz @finish

;invoke RecorsivCanWalk,bl
mov ebx,[esp+4];cell

inc bl
push ebx
call RecorsivCanWalk
cmp found,0
jnz @finish

;invoke RecorsivCanWalk,bl
mov ebx,[esp+4];cell
push ebx
call RecorsivCanWalk

;cmp found,1
;je @finish
;	invoke RecorsivCanWalk,bl
@didntfind:

ret 4
@finish:

mov found,1
ret 4
RecorsivCanWalk endp
``````

thanks

eko
Posted on 2002-09-15 03:43:44 by eko
Here's a working C version that uses depth-first search to find a path. This won't always find the shortest path, but will tell you whether a path can be found or not.

``````
[size=9]#define arrcount(x) (sizeof(x)/sizeof(x[0]))
/*
char board[] = "-----0000"
"------000"
"-------00"
"--------0"
"---------0"
"--------00"
"-------000"
"------0000"
"-----";
*/
char board[] =  "#----0000"
"###-#-000"
"#---###00"
"#-######0"
"---------0"
"#######-00"
"-#-#---000"
"#-#-##0000"
"--#--";

#define BOARDSIZE  81

char boardFormat[] =    "    . . . . .\n"
"   . . . . . .\n"
"  . . . . . . .\n"
" . . . . . . . .\n"
". . . . . . . . .\n"
" . . . . . . . .\n"
"  . . . . . . .\n"
"   . . . . . . \n"
"    . . . . .\n";

int neighbourOffsets[] = {-10,-9,-1,+1,+9,+10};

bool isValidIndex(int index)
{
if (index<0 || index>=BOARDSIZE) return false;
return board[index]!='0';
}

int findNextNeighbour(int curPos, int prevNeighbour)
{
bool bPrevNeighbourFound = false;
for (int i=0;i<arrcount(neighbourOffsets);i++)
{
int curNeighbour = curPos + neighbourOffsets[i];

if (isValidIndex(curNeighbour))
{
if (prevNeighbour==-1) return curNeighbour;
if (curNeighbour==prevNeighbour)
{
bPrevNeighbourFound = true;
}
else if (bPrevNeighbourFound)
{
return curNeighbour;
}
}
}
return -1;
}

void printBoard()
{
char buffer[arrcount(boardFormat)];

int iBoard = 0;

for (int i=0;i<arrcount(boardFormat);i++)
{
if (boardFormat[i]=='.')
{
while (board[iBoard]=='0') iBoard++;
buffer[i] = board[iBoard];
iBoard++;
}
else
{
buffer[i] = boardFormat[i];
}
}
printf(buffer);
}

bool possiblePath(int curPos, int destPos, int trace[], int curDepth = 0)
{

trace[curDepth] = curPos;

if (curPos==destPos)
{
printf("path found!\n");
return true;
}

int prevNeighbour = -1;
int curNeighbour;

while(true)
{
curNeighbour = findNextNeighbour(curPos, prevNeighbour);
if (curNeighbour==-1) break; // done all neighbours

if (board[curNeighbour]=='-') //free piece?
{
// see if neighbour was already visited earlier:
bool bNeighbourVisited = false;
for (int k=0;k<curDepth;k++)
{
if (trace[k]==curNeighbour)
{
bNeighbourVisited = true;
break;
}
}

if (!bNeighbourVisited)
{
if (possiblePath(curNeighbour, destPos, trace, curDepth+1))
{
return true;
}

}
}
prevNeighbour = curNeighbour;
}
trace[curDepth] = -1;
return false;
}

int main(int argc, char* argv[])
{
printf("legenda:\n\n"
"-\tfree space\n"
"#\tused space\n"
"+\tpart of the found path\n\n");

int trace[BOARDSIZE+1];

for (int i=0;i<arrcount(trace);i++) trace[i] = -1;
printf("Board:\n");
printBoard();

if (possiblePath(1, 79, trace))
{
printf("Found path:\n");

int k=0;
while(true)
{
int j = trace[k];
if (j==-1) break;
printf(" %d", j);
board[j] = '+';
k++;
}
printf("\n");
printBoard();
}
else
{
printf("no path found!\n");
}
return 0;

}
[/SIZE]``````

The board array contains the board data ('0' = invalid index, '-' = free space, '#' (or anything else) = used space). The code will try to find a path from index 1 to index 79 and show it.

Here's the result:
``````
legenda:

-       free space
#       used space
+       part of the found path

Board:
# - - - -
# # # - # -
# - - - # # #
# - # # # # # #
- - - - - - - - -
# # # # # # # -
- # - # - - -
# - # - # #
- - # - -
path found!
Found path:
1 2 3 12 21 20 19 28 37 38 39 40 41 42 43 44 53 62 61 60 69 79
# + + + -
# # # + # -
# + + + # # #
# + # # # # # #
- + + + + + + + +
# # # # # # # +
- # - # + + +
# - # + # #
- - # + -
``````

It looks a bit strange but the +-signs show the path found. The numbers are the tiles visited. I've attached the compiled program.

Thomas
Posted on 2002-09-15 05:52:16 by Thomas
and what is : and ?

"?" and ":" in C are part of conditional expression.

a += ( b < 4 ) ? b : 1;

is exactly the same as...

if( b < 4 )
{ a = a + b; }
else
{ a = a + 1 }

iblis:can you explain alittle how does it work ?

Basically what you'd be doing is assigning each hexagon-cell an x,y,z value so that you can easily traverse each direction of the board. By incrementing/decrementing either x, y or z and then translating that value to its array index, you can check if a hexagon-cell in a certain direction is occupied/moveable. How you do this is unimportant as long as you have some way of translating x,y,z to its corresponding cell.

In the diagram below I changed the rules a bit. x, y, and z diverge outward from the center. This way you can easily adjust the size of the board if you want. ( The number of cells on a board like this is 3r?-3r+1 where r is the number of cells from the center to any corner. )

Note that in each cell in the diagram, z = y - x, so you really only need to store x and y.
Posted on 2002-09-16 02:38:19 by iblis
Thomas : thanks!
i think i have done the same . or closer

i have wrote a function that insert into an array all the freeplaces

and then search in recursiv for the destinion while adding (-9,1,10,-9,-1,10)
until it finds
so it doesnt search for the shortest way just check if there is one

iblis : nice . i need to check this way more closer

i have a question: how do you make these picuters?

thanks all
bye

eko
Posted on 2002-09-16 13:33:53 by eko
hiiii

i forgot to publish my game
i made it for an Israel Computer contest that the prize of the contest is some "money ticket to an Computer shop in here"

here is it
a made the board in an array of 9 on9
so i can more easly access other cells

its like
x-10 x - 9
x- 1 x x + 1
x+9 x - 9

there is a loss of 81-61 bytes
but i used someof those lost bytes as a varibles

this way has been done only becuase i had very little time to work on the game ...
if I build such a game with more time . place the board in 61 bytes array and not 81
but
any away

bye

eko
stop talking / writing

EDIT:
there are some crazy thing in there becuase the lack of time .
and its not finish
so dont pay attention
Posted on 2002-09-24 16:06:03 by eko

iblis : nice . i need to check this way more closer

i have a question: how do you make these picuters?
iblis, ?C?mo usted hace estos picuters?
Posted on 2002-09-24 19:24:14 by bitRAKE
Erm, eh... The same way anybody else makes 'em. Any graphics program would do it, Photoshop, Illustrator etc. Heck MS Paint could do it.

I don't see anything special about it. :confused:
Posted on 2002-09-24 22:59:39 by iblis

I don't see anything special about it. :confused:
Well, it would take some time for me to make that image in the software I have here. Surely a sign of your illustrative skills! I have M\$ Visio for illustrative stuff - it has paid for itself a couple times over. It is similar to Excel - good for many things, great for nothing. When you can't afford much software, but want to do a variety of things - it is a good purchase.
Posted on 2002-09-24 23:53:50 by bitRAKE
eko, I think you forgot to preserve esi/edi/ebx somewhere. The game kept crashing on my win2k machine until I added uses esi edi ebx to WndProc..

Thomas
Posted on 2002-09-25 12:38:47 by Thomas