A* 알고리즘 (몬스터 길찾기)

몬스타 길찾기 알고리즘입니다.

점팩에서 찾아서 올립니다.

주석 처리 되어있는것으로 보아 문제점이 있는것 같습니다.

아마 똑같은경로 재탐색으로 인해 발생되는 오류이거나 케릭터위치 바뀔경우 못찾아서 무한루프가능성 같네요(아닐수도 ^^;)

그냥 자료있길래 올렸는데 제대로 실행되는지는 모르겠습니다.

돌아다니는 팩중에서 발췌했습니다

그리고 소스출처는 잇뽕님으로 되있네요

문제가 된다면 자삭하겠습니다.

장점: 빠른시간안에 결과를 만들어서 다른알고리즘에 비해 평균적으로 우수한 속도 자랑합니다.

        본섭처럼 똑똑한 몬스터가 되겠죠?

단점: 검색 공간의 크기가 크다는점 (자칫 잘못 소스짜면 cpu와 메모리 리소스 크게 차지합니다.)

        똑같은 경로를 재탐색할경우 무한루프 가능성(재탐색 못하게 걸러주는 조건 필요할것 같아요)

        맵의크기에따라 리소스 차지하는게 기하급수적이라는것

내생각이지만 보강이 필요하다

1. 몬스터가 걸어서 갈수없는 부분에 케릭터가 갈경우 경로를 탐색하지 못하게 하는것도 조건에 걸어주는것

2. 문이나 출구가 있다면 첫번째 목표를 문이나 출구로 설정해서 경로 검색

3. 항상 케릭터가 텔을 할경우나 위치가 바뀌는 경우 경로가 재탐색되어야 할것이며 맵에 없다면 초기화

4. 던전지역 제외 맵이 큰 본토지역은 쓰지말것 (큰맵은 기존의 방식 길찾기로 해주면 될듯)

알고리즘 설명은

http://blog.naver.com/nsunlee?Redirect=Log&logNo=130048768455 

이블로그 보시면 될듯해요

L1Npcinstance.java

     if (dir == -1) {
      tagertClear();

     } else {
      if (onAStar(target, true)) {  // 대상까지 이동할 수 있기때문에 A* 알고리즘을 작동한다
       onAStar(target, false);
      } else {       // 대상까지 이동할 수 없기때문에 랜덤워크를 작동한다
       randomWalk();
      }
     }
         for (Object object : L1World.getInstance().getObject()) {
      L1DoorInstance door = (L1DoorInstance) object;
      if (door.getPassable() == L1DoorInstance.NOT_PASS) {
       getMap().setPassable(door.getLocation(), false);
       setSleepTime(calcSleepTime(getPassispeed()));
      }
     }

그냥 끝부분에 적당히 넣어주세요

 public boolean onAStar(L1Character target, boolean check) {
  return onAStar(target.getX(), target.getY(), target.getMapId(), check);
 }

 public boolean onAStar(int tx, int ty, int mapId, boolean check) {
  // check: true - 경로를 확인만 한다, false - 검색된 경로를 이동시킨다
  pfAStar = new L1Astar();
  iPath = new int[300][2];
  // 최단경로를 검색한다
  nodePath = pfAStar.FindPath(this, tx, ty, mapId);
  // 현재경로 카운터를 초기화한다
  iCurrentPath = 0;
  // 경로목록을 만든다
  while ( nodePath != null ) {
   iPath[iCurrentPath][0] = nodePath.x;
   iPath[iCurrentPath][1] = nodePath.y;
   iCurrentPath++;
   nodePath = nodePath.prev;
  }
  // 최대경로 카운터에 현재경로 카운터를 대입한다
  iMaxPath = iCurrentPath;
  // 확인목적이 아니고 목표경로가 대상과 0 또는 1, 2 타일 거리일 경우에만 이동시킨다
  // 대상의 직접위치는 이동불가(검색불가) 위치이기때문에 0 타일은 될 수 없다
  int tile = Math.max(Math.abs(iPath[0][0] - tx), Math.abs(iPath[0][1] - ty));
  if (tile < 3) {
   if (check) { // 확인용
    return true;
   } else { // 확인용이 아닌 경우
    iMonsterX = iPath[iCurrentPath-2][0];
    iMonsterY = iPath[iCurrentPath-2][1];
    // 이동할 좌표에 맞게 몹의 방향을 설정한다
    if (getX()    <  iMonsterX && getY()  >  iMonsterY) {
     setHeading(1);
    } else if (getX()  <  iMonsterX && getY()  ==  iMonsterY) {
     setHeading(2);
    } else if (getX()  <  iMonsterX && getY()  <  iMonsterY) {
     setHeading(3);
    } else if (getX()  ==  iMonsterX && getY()  <  iMonsterY) {
     setHeading(4);
    } else if (getX()  >  iMonsterX && getY()  <  iMonsterY) {
     setHeading(5);
    } else if (getX()  >  iMonsterX && getY()  ==  iMonsterY) {
     setHeading(6);
    } else if (getX()  >  iMonsterX && getY()  >  iMonsterY) {
     setHeading(7);
    } else if (getX()  ==  iMonsterX && getY()  >  iMonsterY) {
     setHeading(0);
    }
    // 이동시킨다
    getMap().setPassable(getLocation(), true);
    setX(iMonsterX);
    setY(iMonsterY);
    getMap().setPassable(getLocation(), false);
    broadcastPacket(new S_MoveCharPacket(this));
    setSleepTime(calcSleepTime(getPassispeed()));
    // 노드를 초기화 한다
    pfAStar.ResetPath();
    // 테스트용 메세지를 출력한다
    //System.out.println(" 경로: " + (iMaxPath - 1) + " | " +
    //  "거리: " + Math.max(Math.abs(getX() - tx), Math.abs(getY() - ty)));
   }
  }
  // 목표경로가 2 타일 이상 차이가 있다면 대상을 초기화한다
  // 길이 존재하지 않거나 막혀있기 때문이다
  else {
   tagertClear();
   return false;
  }
  return true;
 }

 private void randomWalk() {
  tagertClear();
  int dir = checkObject(getX(), getY(), getMapId(), getRnd()
    .nextInt(20));
  if (dir != -1) {
   setDirectionMove(dir);
   setSleepTime(calcSleepTime(getPassispeed()));
  }
 }
 public int calcSleepTime(int i) {
  int sleepTime = i;
  switch (getMoveSpeed()) {
  case 0: break;
  case 1: sleepTime -= (sleepTime * 0.25); break;
  case 2: sleepTime *= 2; break;
  }
  if (getBraveSpeed() == 1) {
   sleepTime -= (sleepTime * 0.25);
  }
  return sleepTime;
 }