homepage Welcome to WebmasterWorld Guest from 54.166.113.249
register, free tools, login, search, pro membership, help, library, announcements, recent posts, open posts,
Pubcon Platinum Sponsor 2014
Home / Forums Index / Code, Content, and Presentation / JavaScript and AJAX
Forum Library, Charter, Moderator: open

JavaScript and AJAX Forum

    
Complicated next-to script
Is there a way?
adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 1:00 am on Nov 16, 2004 (gmt 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?

 

Bernard Marx

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 11:20 am on Nov 16, 2004 (gmt 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?

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 1:06 pm on Nov 16, 2004 (gmt 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.

Bernard Marx

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 2:57 pm on Nov 16, 2004 (gmt 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

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 9:40 pm on Nov 16, 2004 (gmt 0)

Yes.

Bernard Marx

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 9:55 pm on Nov 16, 2004 (gmt 0)

..almost there, but it'll have to wait till morning.

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 10:59 pm on Nov 16, 2004 (gmt 0)

Thank you so much, in advance!

Bernard Marx

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 11:48 am on Nov 17, 2004 (gmt 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]

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 3:29 am on Dec 24, 2004 (gmt 0)

But how can this be used to detect if two characters are connected?

MikeFoster

10+ Year Member



 
Msg#: 2737 posted 3:24 pm on Dec 24, 2004 (gmt 0)

Nice work, Bernard!

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 3:03 am on Dec 25, 2004 (gmt 0)

I second that.

orion_rus

10+ Year Member



 
Msg#: 2737 posted 8:48 pm on Dec 25, 2004 (gmt 0)

adni18, why don't u make this puzzle a multilevel array, and checking connection would be so simple.

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 12:51 am on Dec 26, 2004 (gmt 0)

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

What do you mean 'a multilevel array'?

orion_rus

10+ Year Member



 
Msg#: 2737 posted 12:21 pm on Dec 26, 2004 (gmt 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

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 7:18 pm on Dec 26, 2004 (gmt 0)

The only problem is that I'm not sure in which direction the letters will go. The user controls it.

orion_rus

10+ Year Member



 
Msg#: 2737 posted 7:56 pm on Dec 26, 2004 (gmt 0)

hmm, but can u explain it? i don't clear understand u? u need a start point or something else?

adni18

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 3:08 am on Dec 27, 2004 (gmt 0)

I think bernard's code works fine.

Bernard Marx

WebmasterWorld Senior Member 10+ Year Member



 
Msg#: 2737 posted 3:54 pm on Dec 31, 2004 (gmt 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.

Global Options:
 top home search open messages active posts  
 

Home / Forums Index / Code, Content, and Presentation / JavaScript and AJAX
rss feed

All trademarks and copyrights held by respective owners. Member comments are owned by the poster.
Home ¦ Free Tools ¦ Terms of Service ¦ Privacy Policy ¦ Report Problem ¦ About ¦ Library ¦ Newsletter
WebmasterWorld is a Developer Shed Community owned by Jim Boykin.
© Webmaster World 1996-2014 all rights reserved