관리 메뉴

Define You

Robocode 마스터의 비밀: Factored wall avoidance 본문

Insight for 기획/기획을 하고싶은 학생

Robocode 마스터의 비밀: Factored wall avoidance

하루10분 2007.06.07 10:57

출처 : http://www.ibm.com/developerworks/kr/library/j-fwa/index.html



코너에 갇히거나 원하는 이동 방향에서 너무 많이 벗어나지 않으면서, 로봇과 벽 사이의 간격을 유지하는 알고리즘은 간단히 만들 수 없는 것 같습니다. 한 가지 간단한 솔루션으로, Factored wall avoidance가 있습니다. 이 글에서, David McCoy가 이를 구현하는 방법을 설명합니다.

With a few additions to the bot we built in "상대편의 움직임 추적하기"에서 구현했던 로봇에 몇 가지를 더 추가하여, 기존의 움직임 알고리즘 또는 문제가 많은 움직임 알고리즘에 Factored Wall Avoidance를 추가할 수 있다. Factored Wall Avoidance는 자신의 로봇과 벽의 근접성에 따라서 안전한 방향 설정(heading)으로 원하는 방향을 팩토링 함으로써 최상의 방향을 찾는 것이다.

일반 수학적 계산에 헬퍼 메소드 추가하기

우선 자주 사용되는 수학적 알고리즘에 헬퍼 메소드를 로봇에 추가한다.

calculateBearingToXYRadians() 메소드는 java.lang.Math 메소드 atan2()를 사용하여 sourceX,sourceY에서 targetX,targetY까지 절대 위치(absolute bearing)를 계산한 다음, 이 값을 sourceHeading에 관련된 위치로 변환한다.

그리고 normalizeAbsoluteAngleRadians() 메소드와 normalizeRelativeAngleRadians() 메소드도 필요하다.


Listing 1. 수학 헬퍼 메소드

                

private static final double DOUBLE_PI = (Math.PI * 2);
private static final double HALF_PI = (Math.PI / 2);

public double calculateBearingToXYRadians(double sourceX, double sourceY,
    double sourceHeading, double targetX, double targetY) {
        return normalizeRelativeAngleRadians(
           Math.atan2((targetX - sourceX), (targetY - sourceY)) -
               sourceHeading);
    }

public double normalizeAbsoluteAngleRadians(double angle) {
   if (angle < 0) {
        return (DOUBLE_PI + (angle % DOUBLE_PI));
    } else {
        return (angle % DOUBLE_PI);
    }
}

public static double normalizeRelativeAngleRadians(double angle) {
    double trimmedAngle = (angle % DOUBLE_PI);
    if (trimmedAngle > Math.PI) {
        return -(Math.PI - (trimmedAngle % Math.PI));
    } else if (trimmedAngle < -Math.PI) {
        return (Math.PI + (trimmedAngle % Math.PI));
    } else {
        return trimmedAngle;
    }
}




위로


AdvancedRobot을 back-as-front 기능으로 확장하기

다음으로, 로봇을 반대로 이동시키기 위한 back-as-front 기능을 제공하기 위해 AdvancedRobot 클래스 기능을 몇 가지 헬퍼 메소드로 확장할 필요가 있다.

  • getRelativeHeading() 메소드는 로봇의 현재 위치와 관련하여 정확한 방향을 계산한다.

  • reverseDirection() 메소드는 매우 단순하다. direction 인스턴스 변수를 토글링(toggle) 하고 로봇의 방향을 바꾼다. 감속할 때에는 시간이 걸리기 때문에 로봇은 속도에 따라서, 방향을 바꾸기 전에 최대 네 개의 프레임까지 같은 방향으로 움직일 수도 있다.

  • setAhead()setBack() 메소드는 AdvancedRobot 클래스에서 같은 이름의 메소드를 오버라이드 한다. 현재 방향에 대한 로봇의 속도를 설정하고, direction 인스턴스 변수를 필요에 따라 조정한다. 비례 연산은 로봇이 현재 움직이고 있는 방향과 관련이 있다.

  • setTurnLeftRadiansOptimal()setTurnRightRadiansOptimal() 메소드는 (Math.PI / 2) 보다 크게 회전하여 로봇의 방향을 바꾼다. adjustHeadingForWalls 메소드를 사용할 때 이러한 메소드들을 사용해야 하는데, 나중에 설명하겠다.

주: getter와 setter 메소드를 사용하는 대신 direction 인스턴스 변수에 직접 액세스 한다. 이것은 좋은 방법은 아니지만, 나는 내 로봇 코드에 이를 수행하여 데이터 액세스 속도를 높이곤 한다.


Listing 2. 로봇 헬퍼 메소드

                


public double getRelativeHeadingRadians() {
    double relativeHeading = getHeadingRadians();
    if (direction < 1) {
        relativeHeading =
                normalizeAbsoluteAngleRadians(relativeHeading + Math.PI);
    }
    return relativeHeading;
}

public void reverseDirection() {
    double distance = (getDistanceRemaining() * direction);
    direction *= -1;
    setAhead(distance);
}

public void setAhead(double distance) {
    double relativeDistance = (distance * direction);
    super.setAhead(relativeDistance);
    if (distance < 0) {
        direction *= -1;
    }
}

public void setBack(double distance) {
    double relativeDistance = (distance * direction);
    super.setBack(relativeDistance);
    if (distance > 0) {
        direction *= -1;
    }
}

public void setTurnLeftRadiansOptimal(double angle) {
    double turn = normalizeRelativeAngleRadians(angle);
    if (Math.abs(turn) > HALF_PI) {
        reverseDirection();
        if (turn < 0) {
            turn = (HALF_PI + (turn % HALF_PI));
        } else if (turn > 0) {
            turn = -(HALF_PI - (turn % HALF_PI));
        }
    }
    setTurnLeftRadians(turn);
}

public void setTurnRightRadiansOptimal(double angle) {
    double turn = normalizeRelativeAngleRadians(angle);
    if (Math.abs(turn) > HALF_PI) {
        reverseDirection();
        if (turn < 0) {
            turn = (HALF_PI + (turn % HALF_PI));
        } else if (turn > 0) {
            turn = -(HALF_PI - (turn % HALF_PI));
        }
    }
        setTurnRightRadians(turn);
}




위로


Factored Wall Avoidance 추가하기

우리가 추가할 마지막 메소드는 adjustHeadingForWalls()이다.

이 메소드의 초반부는 벽과의 근접성에 기반하여 안전한 x,y 위치를 선택한다. (이것은 로봇의 현재 x 또는 y 좌표 또는 로봇이 벽에 가까이 있을 경우 중심점이 될 것이다.) 이 메소드의 후반부는 "안전한" 방향을 계산하고 로봇이 벽에 얼마나 근접해 있는가에 비례하여 원하는 방향으로 이를 팩토링 한다.

로봇이 벽으로 나아가는 정도는 WALL_AVOID_INTERVALWALL_AVOID_FACTORS 상수를 사용하여 조정될 수 있다.


Listing 3. 벽 피하기 메소드

                

private static final double WALL_AVOID_INTERVAL = 10;
private static final double WALL_AVOID_FACTORS = 20;
private static final double WALL_AVOID_DISTANCE =
        (WALL_AVOID_INTERVAL * WALL_AVOID_FACTORS);

private double adjustHeadingForWalls(double heading) {
    double fieldHeight = getBattleFieldHeight();
    double fieldWidth = getBattleFieldWidth();
    double centerX = (fieldWidth / 2);
    double centerY = (fieldHeight / 2);
    double currentHeading = getRelativeHeadingRadians();
    double x = getX();
    double y = getY();
    boolean nearWall = false;
    double desiredX;
    double desiredY;

    // If we are too close to a wall, calculate a course toward 
    // the center of the battlefield.
    if ((y < WALL_AVOID_DISTANCE) ||
            ((fieldHeight - y) < WALL_AVOID_DISTANCE)) {
        desiredY = centerY;
        nearWall = true;
    } else {
        desiredY = y;
    }
    if ((x < WALL_AVOID_DISTANCE) ||
            ((fieldWidth - x) < WALL_AVOID_DISTANCE)) {
        desiredX = centerX;
        nearWall = true;
    } else {
        desiredX = x;
    }

    // Determine the safe heading and factor it in with the desired 
    // heading if the bot is near a wall
    if (nearWall) {
        double desiredBearing = 
           calculateBearingToXYRadians(x, 
                                       y, 
                                       currentHeading, 
                                       desiredX, 
                                       desiredY);
        double distanceToWall = Math.min(
                Math.min(x, (fieldWidth - x)),
                Math.min(y, (fieldHeight - y)));
        int wallFactor =
                (int)Math.min((distanceToWall / WALL_AVOID_INTERVAL),
                              WALL_AVOID_FACTORS);
        return ((((WALL_AVOID_FACTORS - wallFactor) * desiredBearing) +
                 (wallFactor * heading)) / WALL_AVOID_FACTORS);
    } else {
        return heading;
    }
}




위로


결론

나머지는 쉽다. 현재의 네비게이션 알고리즘을 사용하고 adjustHeadingForWalls() 메소드를 통해 그 결과를 제공함으로써 벽을 피할 수 있다.

단순하게 하기 위해 로봇 예제(다운로드)는 방향 변경에 0을 요청하여 직선 라인으로 움직일 것이다.


Listing 4. 벽 피하기 메소드

                


public void run() {
    while(true) {
        setTurnRightRadiansOptimal(adjustHeadingForWalls(0));
        setAhead(100);
        execute();
    }
}

이제 다 되었다. 간단하지만, 효과적이다.

기사의 원문보기





위로


다운로드 하십시오

설명 이름 크기 다운로드 방식
Source code j-fwa.zip 4KB HTTP
다운로드 방식에 대한 정보


참고자료

  • Robocode 마스터의 비밀 : 로보코드 마스터들이 주는 힌트, 팁, 조언 (한글)

  • 로보코드 창시자, Mathew Nelson은 공식 로보코드 사이트를 관리하고 있다. 로보코드에 대해 진지하게 검토중인 사람이라면 한번쯤은 들러야 한다. 요청을 받은 기능들이 들어 있는 "always current" 리스트에서 to-do list 리스트도 확인해 보기 바란다.

  • Christian Schnell의 RoboLeague는 로보코드 리그 매니저 겸 시즌 매니저이다. 여러가지 그룹핑을 통해서 시합을 펼치고, 결과를 관리하며, HTML로 된 현황 리포트를 만들어 낸다.

  • "Rock 'em, sock 'em Robocode (한글)" (한국 developerWorks, 2002년 1월) 총알을 피하고 정확한 공격 작전을 수행하면서 상속, 다형성, 이벤트 처리 및 내부 클래스를 배우는 것이 가능할까? 중독적인 게임광 대상 교육 툴인 Robocode가 전 세계 자바 개발자들에게 이를 가능하도록 한다.

  • "Rock 'em, sock 'em Robocode: 제 2 라운드 (한글)" (한국 developerWorks, 2002년 5월), 고급 로봇 구현과 팀 플레이로 기본에서 나아가기.

  • 자바에 입문했다면 체크하라. "자바 프로그래밍 소개" (developerWorks, 2004년 11월)

  • 한국 developerWorks 자바 존: 자바 프로그래밍 관련 다양한 기술자료 보기



 

필자소개

David McCoy는 동료에게서 Robocode에 대한 이야기를 듣고 바로 매료되었다. 그가 만든 로봇인 droid.PrairieWolf는 Gladiatorial League에서 상위에 랭크 되었었다. (dsmccoy@velocitus.net)

0 Comments
댓글쓰기 폼