שלום, אני מנסה לבנות אלגוריתם שימצא דרך אפשרית במבוך (מטריצה), בשפת ג'אווה.
בניתי אלגוריתם שפועל על מטריצה (19 על 19) שמרכיב לוח משחק עם 9 על 9 משבצות לשחקנים, בין כל משבת יש תא שהוא מקום לחומה וכמובן מסביב ללוח יש מסגרת חומות.
אז להן אם בתא יש 2 סימן שאין חומה, אם יש משהו אלר סימן שיש ואין מעבר למשבצת הבאה. אני עכשיו אכתוב את הקוד, ואם מישהו רואה טעות או יוכל לעזור, אנא זה זה חשוב.
m-כמות הצעדים שחייל יכול לזוז על מנת להגיעה לפתרון, סתם בשביל העניין עכשיו זה עומד על 81
תודה מראש
הקוד:

public boolean check_walls (int mat[][],int x, int y, int m)
{
int win=9;
if (m==0)
{
//JOptionPane.showMessageDialog(null,"check1");
return false;
}
else
{
if ((y+1==win) && (mat[y*2][x*2-1]==2))
return true;
if ((mat[y*2][x*2-1]==2) && (mat[y*2-2][x*2-1]==2))
{
if (check_walls(mat,x,y+1,m-1) || check_walls(mat,x,y-1,m-1))
return true;
}
else
if (mat[y*2][x*2-1]==2)
{
if (check_walls(mat,x,y+1,m-1))
return true;
}
else
if ((mat[y*2-1][x*2]==2) && (mat[y*2-1][x*2-2]==2))
{
if (check_walls(mat,x+1,y,m-1) || check_walls(mat,x-1,y,m-1))
return true;
}
else
if (mat[y*2-1][x*2]==2)
{
if (check_walls(mat,x+1,y,m-1))
return true;
}
else
if (mat[y*2-1][x*2-2]==2)
{
if (check_walls(mat,x-1,y,m-1))
return true;
}
else
if (mat[y*2-2][x*2-1]==2)
{
if (check_walls(mat,x,y-1,m-1))
return true;
}
//JOptionPane.showMessageDialog(null,"check2");
return false;
}
}

אני רוצה להמליץ לך על אלגוריתם אומנם יותר קשה אבל הרבה יותר אפקטיבי. האלגוריתם נקראה
Astar (A*)
הוא מוצא את הדרך הטובה ביותר והקצרה ביותר בין שני נקודות. האלגוריתם אומנם לא פשוט אבל אני הצלחתי ליישם אותו אחרי 3 ניסיונות.
ניתן לקרוא על האלגוריתם פה:
http://en.wikipedia.org/wiki/A*_search_algorithm
או פה
http://www.policyalmanac.org/games/aStarTutorial.htm

אומנם לא עזרתי לך בדרך שלך אז אני מראש מצטער אם זה לא מה שרצית.

תודה לך האלגוריתם! אמ לפני שאני מתעמק בו רציתי לשאול אותך אם יש אפשרות ליישם אותו במטריצה?

כשאת אומר מטריצה אתה מתכוון למערך של תאים? אם זה הכוונה שלך אז כן ניתן ליישם אותו במטריצה אני עשיתי אותו על מפה שהיא מערך בגודל Xעל Y

לבסוף שיפרתי את האלגוריתם שלי ועכשיו אני אפרסם למעוניינים...
רציתי לבקש ממך אם אתה יכול בבקשה לפרסם את האלגוריתם A* שבנית למערך תאים.

להלן הקוד המתוקן שלי :

public boolean check_wallsb (int mat[][],int x, int y, int m)
{
int win=9,i,j;
/* for (i=0;i<19;i++)
{
for (j=0;j<18;j++)
System.out.print(mat[i][j]);
System.out.println(mat[i][j]);
}*/
//JOptionPane.showMessageDialog(null,x);
//JOptionPane.showMessageDialog(null,y);


// JOptionPane.showMessageDialog(null,"->");
// currentB.setData(x*50+8,y*50+8,25,25);
// repaint();


if (m==0)
{
// JOptionPane.showMessageDialog(null,"check1");
return false;
}
else
{
if ((y+1==win) && (mat[y*2][x*2-1]==2))
return true;
if ((mat[y*2][x*2-1]==2) && (mat[y*2-2][x*2-1]==2))
{
mat[y*2-2][x*2-1]=0;
mat[y*2][x*2-1]=0;
mat[y*2-1][x*2]=0;
mat[y*2-1][x*2-2]=0;
if (check_wallsb(mat,x,y-1,m-1) || check_wallsb(mat,x,y+1,m-1))
return true;

}
else
if (mat[y*2][x*2-1]==2)
{

if (check_wallsb(mat,x,y+1,m-1))
return true;
}
else
if ((mat[y*2-1][x*2]==2) && (mat[y*2-1][x*2-2]==2))
{
mat[y*2-2][x*2-1]=0;
mat[y*2][x*2-1]=0;
mat[y*2-1][x*2]=0;
mat[y*2-1][x*2-2]=0;
if (check_wallsb(mat,x+1,y,m-1) || check_wallsb(mat,x-1,y,m-1))
return true;
}
else
//
if ((mat[y*2-1][x*2]==2) && (mat[y*2-2][x*2-1]==2))
{
//JOptionPane.showMessageDialog(null,"right");
mat[y*2-2][x*2-1]=0;
mat[y*2][x*2-1]=0;
mat[y*2-1][x*2]=0;
mat[y*2-1][x*2-2]=0;
if (check_wallsb(mat,x+1,y,m-1) || check_wallsb(mat,x,y-1,m-1))
return true;
}
else
if ((mat[y*2-1][x*2-2]==2) && (mat[y*2-2][x*2-1]==2))
{
//JOptionPane.showMessageDialog(null,"left");
mat[y*2-2][x*2-1]=0;
mat[y*2][x*2-1]=0;
mat[y*2-1][x*2]=0;
mat[y*2-1][x*2-2]=0;
if (check_wallsb(mat,x-1,y,m-1) || check_wallsb(mat,x,y-1,m-1))
return true;
}
else
//
if (mat[y*2-1][x*2]==2)
{

if (check_wallsb(mat,x+1,y,m-1))
return true;
}
else
if (mat[y*2-1][x*2-2]==2)
{

if (check_wallsb(mat,x-1,y,m-1))
return true;
}
else
if (mat[y*2-2][x*2-1]==2)
{
mat[y*2-2][x*2-1]=0;
mat[y*2][x*2-1]=0;
mat[y*2-1][x*2]=0;
mat[y*2-1][x*2-2]=0;
if (check_wallsb(mat,x,y-1,m-1))
return true;
}
// JOptionPane.showMessageDialog(null,"check2");
return false;
}
}

האלגוריתם לא הכי מושלם אבל הוא עובד

קוד:

//Pathfind.h

/* Coded by eXtruct aka Temp aka Dima */
/* Do not copy without permission!		 */
#ifndef _PATHFIND_H
#define _PATHFIND_H

#include <list>
#include "map.h"

typedef struct aPoint_type{
 int x, y;
}aPoint;

enum onListEnum{
 NotOnList=0,
 onOpenList,
 onCloseList
};

typedef struct aNode_type{
 aPoint parent;
 int Gcost;
 int Hcost;
 int Fcost;
 int onList;
}aNode;

typedef std::list<aPoint> Path;

class Astar{
 private:
  Path path;
  aNode *node;
  
  int mX, mY;
  
  bool ListEmpty();
  
  void minFcost(int *x, int *y);
 public:
  Astar();   //Constructor;
  
  ~Astar();   //Destructor
  
  void AstarInit(Map *map);   //Init
  
  void AstarClear();   //Clear all
  
  int AstarSearchPath(int srcX, int srcY, int dstX, int dstY, Map *map);
  
  aPoint AstarGetStep();
};

#endif


//pathfind.cpp

/* Coded by eXtruct aka Temp aka Dima */
/* Do not copy without permission!		 */

#include "pathfind.h"
#include <iostream>

Astar::Astar()
{
 path.clear();
}

Astar::~Astar()
{
	delete []node;
	path.clear();
}

void Astar::AstarInit(Map *map)
{
 map->MapGetSize(&mX, &mY);
 node = new aNode[(mX*mY)];
 path.clear();
 for(int i = 0; i < (mX * mY); i++)
 {
  node[i].parent.x = 0;
  node[i].parent.y = 0;
  node[i].Gcost = -1;
  node[i].Fcost = -1;
  node[i].Hcost = -1;
  node[i].onList = NotOnList;
 }
}

void Astar::AstarClear()
{
 delete []node;
	//path.clear();
}

bool Astar::ListEmpty()
{
 int i;
 for(i = 0; i < (mX * mY); i++)
  if(node[i].onList == onOpenList)
   return false;
 return true;
}

void Astar::minFcost(int *x, int *y)
{
 int min = 10000;
 int minX, minY;
 int i, j;
 for(j = 0; j < mY; j++)
  for(i = 0; i < mX; i++)
   if((node[i + (j * mX)].onList == onOpenList) &&
	  (node[i + (j * mX)].Fcost) != -1)
	if(node[i + (j * mX)].Fcost < min)
	{
	 min = node[i + (j * mX)].Fcost;
	 minX = i;
	 minY = j;
	}
 *x = minX;
 *y = minY;
}

int Astar::AstarSearchPath(int srcX, int srcY, int dstX, int dstY, Map *map)
{
 bool found = false;
 aPoint current;
 int i, j;
 int cX, cY;
 int Gcost;
 
 if((srcX == dstX) && (srcY == dstY))
  return (-1);
  
 if(map->MapGetBlockStatus(dstX, dstY) == NOT_PASSABLE)
  return (-1);
  
 current.x = srcX;
 current.y = srcY;
 node[srcX + (srcY * mX)].parent.x = srcX;
 node[srcX + (srcY * mX)].parent.y = srcY;
 node[srcX + (srcY * mX)].Gcost = 0;
 node[srcX + (srcY * mX)].Hcost = (int)(abs(srcX-dstX) + abs(srcY-dstY));
 node[srcX + (srcY * mX)].Fcost = node[srcX + (srcY * mX)].Gcost +
								  node[srcX + (srcY * mX)].Hcost;
 node[srcX + (srcY * mX)].onList = onOpenList;
 
 while((!ListEmpty()) && (!found))
 {
  minFcost(&current.x, &current.y);
   
  node[current.x + (current.y * mX)].onList = onCloseList;
  
  for(j = -1; j <= 1; j++)
   for(i = -1; i <= 1; i++)
   {
	if((i == 0) && (j == 0))
	 continue;
	
	cX = i + current.x;
	cY = j + current.y;
	
	if((cX < 0) || (cX > mX) || (cY < 0) || (cY > mY))
	 continue;
	 
	if((cX > (WSCREEN / WBLOCK)) || (cY > (HSCREEN / HBLOCK)))
	 continue;
	 
	if(node[cX + (cY * mX)].onList == onCloseList)
	 continue;
	 
	if(map->MapGetBlockStatus(cX, cY) == NOT_PASSABLE)
	 continue;
	 
	if((i != 0) && (j != 0))
	{
	 if((map->MapGetBlockStatus(current.x, current.y + j) == NOT_PASSABLE) &&
		(map->MapGetBlockStatus(current.x + i, current.y) == NOT_PASSABLE))
	  continue;
	}
	
	Gcost = node[current.x + (current.y * mX)].Gcost +
			((i == 0 || j == 0) ? 10 : 14);
	
	if(node[cX + (cY * mX)].onList != onOpenList)
	{
	 node[cX + (cY * mX)].parent.x = current.x;
	 node[cX + (cY * mX)].parent.y = current.y;
	 node[cX + (cY * mX)].Gcost = Gcost;
	 node[cX + (cY * mX)].Hcost = (int)(abs(cX-dstX) + abs(cY-dstY));
	 node[cX + (cY * mX)].Fcost = node[cX + (cY * mX)].Gcost +
								  node[cX + (cY * mX)].Hcost;
	 if((cX != dstX) || (cY != dstY))
	  node[cX + (cY * mX)].onList = onOpenList;
	 else
	 {
	  node[cX + (cY * mX)].onList = onCloseList;
	  found = true;
	 }
	}
	else if(node[cX + (cY * mX)].onList == onOpenList)
	{
	 if(Gcost < node[cX + (cY * mX)].Gcost)
	 {
	  node[cX + (cY * mX)].Gcost = Gcost;
	  node[cX + (cY * mX)].Fcost = node[cX + (cY * mX)].Gcost +
								   node[cX + (cY * mX)].Hcost;
	  node[cX + (cY * mX)].parent.x = current.x;
	  node[cX + (cY * mX)].parent.y = current.y;
	 }
	}
   }
   
  SDL_Delay(1);
 }
 
 if(found)
 {
  int pX = dstX;
  int pY = dstY;
  int ptX, ptY;
  while((pX != srcX) || (pY != srcY))
  {
   current.x = pX;
   current.y = pY;
   path.push_front(current);
   ptX = node[pX + (pY * mX)].parent.x;
   ptY = node[pX + (pY * mX)].parent.y;
   pX = ptX;
   pY = ptY;
  }
 }
 AstarClear();
 return 0;
}

aPoint Astar::AstarGetStep()
{
 aPoint p;
 if(!path.empty())
 {
  p = path.front();
  path.pop_front();
 }
 else
 {
  p.x = -1;
  p.y = -1;
 }
 return p;
}

כמו שאמרתי זה לא הצורה הנכונה לכתוב אותו במקור הוא נכתב עם שני רשימות ולא עם מערך כמו שאני עשיתי.
Map *map זה בעצם המפה שהיא מערך חד מימדי אשר מיוצגת בצורה הבאה:
map[i + (j*mapSizeX)]
מקווה שעזרתי לך.