Welcome to WebmasterWorld Guest from 23.20.206.245

Forum Moderators: open

Message Too Old, No Replies

Complicated next-to script

Is there a way?

     
1:00 am on Nov 16, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


Hi. I am doing a javascript game, and I have an array like this:

arr=new Array('A','A','B','A','A','B','B','A');

The array is displayed like this:

A A B A
A B B A

I would like a script that can tell if the starting point(2 in the array) is connected (not diagonally) to the end point(5 in the array). The order and start and end point can change, unfortunately. This is for a game, much like PopCap's atomica. Can someone please help me?

11:20 am on Nov 16, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:2047
votes: 0


Hi adni,

I think we need some more info¦clarification:

I would like a script that can tell if the starting point(2 in the array) is connected (not diagonally) to the end point(5 in the array).

1. The 'starting point' is 2 in the array?

2. 'connected' - what does that mean exactly? Does in mean 'in the same column', or 'directly below'?

3. 'end point' is 5?

1:06 pm on Nov 16, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


The end point would be 5, because it goes like this:

A A 2 A
A 5 6 A

The starting point is 2. This is because of this:
"A","A","2","A".
0 1 2 3

Sorry for not making myself clear. By connected, I mean connected vertically and/or horizontally to the end point, by a string of the same letters. For example. The starting and ending points in this setup are bold:

ZZZZZZZZZZZZZZ
ZZZZAZZZZZZZZZ
ZZZZAAAAAZZZZZ
ZZZZZZZZAZZZZZ
ZZZZAAAAAZZZZZ
ZZZZZZZZZZZZZZ

All the A's are connected through a chain of A's. Again, I apologize for not making myself clear.

2:57 pm on Nov 16, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:2047
votes: 0


I'm having a think (it's possible certainly).

Meanwhile, is this a possible arrangement_?:


ZZZZZ[b]AAAA[/b]ZZZZZ
ZZZZ[b]AA[/b]ZZ[b]A[/b]ZZZZZ
ZZZZZZZZ[b]A[/b]ZZZZZ
ZZZZZZZZ[b]A[/b]ZZZZZ
ZZZZ[b]AAAAA[/b]ZZZZZ
ZZZZZZZZZZZZZZ
9:40 pm on Nov 16, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


Yes.
9:55 pm on Nov 16, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:2047
votes: 0


..almost there, but it'll have to wait till morning.
10:59 pm on Nov 16, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


Thank you so much, in advance!
11:48 am on Nov 17, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:2047
votes: 0


This is the best I could do for the moment. It seems to work but...

1. It uses certain global variables. It would be better to work these into local variables of the main array method, or properties of objects. Then, for eg, path searches could be made on different 'grid views' of the same linear array.

2. It doesn't actually return the path - only whether or not it exists.

3. The approach may be overkill.

[pre]
Array.prototype.isConnected = function(iStart, iEnd, nCols)
{
var arr = this;
var nRows = Math.ceil(this.length/nCols);
var node;
var found = false;

walk(new Node(iStart));
return found;

function walk(node)
{
if(node.i==iEnd)
found = true;
var neighbs, neighb, k=-1;
var neighbs = node.getNeighbours();
if(neighbs)
{
while(neighb=neighbs[++k])
walk(neighb)
}
}

}
[blue]
/*------------------------------------------------------------------------------
Node type
------------------------------------------------------------------------------*/
[/blue]
function Node(i)
{
if(!ARR[i]) return null;
this.i = i;
// debug only:// this.val = ARR[i];
NODES[i] = this;
}

Node.prototype =
{
getNeighbours :
function()
{
var nCols = NO_COLUMNS,
neighbs = [],
i = this.i;

if(i >= nCols)// .............up (not 1st row)
test(i-nCols,'up');

if((i+1)%nCols)// ............right (not last col)
test(i+1,'right');

if(i < ARR.length - nCols )// down (not last row)
test(i + nCols,'down');

if(i%nCols) //................ left (not 1st col)
test(i-1,'left');

if(!neighbs.length)
return null;

return this.neighbs = neighbs;

//debug only:// var val = this.val;
//----local------------------------
function test(i,drn)
{
if( ARR[i]==CHAR &&!NODES[i]){
//debug://alert(val+'--> '+ARR[i]+': '+drn)
neighbs.push(new Node(i));
}
}
}
}
[blue]
/*------------------------------------------------------------------------------
START
------------------------------------------------------------------------------*/
[/blue]
var CHAR = 'A'; // accepted 'linking character'
var NO_COLUMNS = 14 ;
var NODES = {} ;
[blue]
/*------------------------------------------------------------------------------
Each character in the array is considered a 'node'. A node object is
created for each one encountered. Each object is placed into the global
NODES array by it's array index.

NODES is a 'sparse' array. Its purpose is to prevent nodes being
investigated more than once, and so prevent endless loops.
------------------------------------------------------------------------------*/
[/blue]
var ARR = (''+
'##############'+
'##AAAA###AAAA#'+
'#####A###A##A#'+
'##AAAAAAAAAAAA'+
'AAA##########A'+
'#######AAAAAAA'+
'####AAAA######'+
'##############').split('');

alert(ARR.isConnected(16,88,NO_COLUMNS))[/pre]

3:29 am on Dec 24, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


But how can this be used to detect if two characters are connected?
3:24 pm on Dec 24, 2004 (gmt 0)

Junior Member

10+ Year Member

joined:July 20, 2001
posts:137
votes: 0


Nice work, Bernard!
3:03 am on Dec 25, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


I second that.
8:48 pm on Dec 25, 2004 (gmt 0)

Preferred Member

10+ Year Member

joined:Oct 3, 2004
posts:598
votes: 0


adni18, why don't u make this puzzle a multilevel array, and checking connection would be so simple.
12:51 am on Dec 26, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


why don't u make this puzzle a multilevel array[?]

What do you mean 'a multilevel array'?

12:21 pm on Dec 26, 2004 (gmt 0)

Preferred Member

10+ Year Member

joined:Oct 3, 2004
posts:598
votes: 0


to easy navigate ur level would be like so
array[0]="ZZZZZ"
array[1]="ZZAZZ"
array[2]="ZZAAZ"
array[3]="ZZZAZ"
and to check the navigation u can check
array[3][3]=="A"?
and check arround would be like so
array[j][i+1]="A" array[j+1][i]="A" and so on...)
what are u think
7:18 pm on Dec 26, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


The only problem is that I'm not sure in which direction the letters will go. The user controls it.
7:56 pm on Dec 26, 2004 (gmt 0)

Preferred Member

10+ Year Member

joined:Oct 3, 2004
posts:598
votes: 0


hmm, but can u explain it? i don't clear understand u? u need a start point or something else?
3:08 am on Dec 27, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:681
votes: 0


I think bernard's code works fine.
3:54 pm on Dec 31, 2004 (gmt 0)

Senior Member

WebmasterWorld Senior Member 10+ Year Member

joined:Apr 15, 2004
posts:2047
votes: 0


Thanks. It's OK, but it was really the quickest solution I could come up with.
I reckon the problem itself must be a 'classic' of some kind.

The problems are:
1. the path itself isn't returned.
2. The algorithm uses a recursive function. I guess this means that the function stack is built up to the extent of each searched path before it collapses. I have no idea how big the stack can be. This probably isn't a problem if the 'maze' isn't too large.

Re multi-dim arrays: Adni was using a string, so I stuck with it, just splitting it into a single array, rather than a 2D. In the end the algorithm is the same. The same basic idea could be used on just the original string itself.

If it's a classic problem, then I guess the classic solution would be to create a single iterator object that searches the maze, keeping track of the path home. Guaranteeing the shortest path may well be a bigger problem.