Java项目开发与毕业设计指导 朱福喜, 黄昊编著 清华大学出版社 项目2
源代码在线查看： ant.java
package ant;
import java.util.Random;
import org.eclipse.swt.graphics.Color;
import org.eclipse.swt.graphics.GC;
import util.PosList;
import util.Position;
import util.PosList.PosListIterator;
/** 蚂蚁类，
* 控制每个独立蚂蚁行为
* @author Leaf
*/
public class Ant {
/** 标识 */
int id;
/** 路径长度 */
int tourLength;
/** 全局最短路径长度 */
static int minTourLength;
/** 已访问路径 */
PosList tour = new PosList();
/** 已知最短路径 */
static PosList minTour = new PosList();
/** 主方向 */
private int section;
private double slope;
/** 增量计算 */
private int d, incrE, incrNE;
/** 目前位置 */
Position now;
/** 上一个位置 */
Position last;
/** 出发地 */
Position from;
/** 目的地 */
Position to;
/** 探索概率 */
static double pExplore = 0.05;
/** 随机扰动概率 */
static double pDisturb = 0.1;
/** 前向参考概率 */
static double pLookForward = 0.7;
boolean lookingForward = false;
static int forwardOutTimes;
int forwardCounter;
static int forwardMinLength = 20;
static int forwardMaxLength = 100;
/** 随机数发生器 */
static Random rand = new Random();
/** 当前环境 */
static Environment currentEnvironment;
/** 路径优化长度 */
public static int optLength;
/** 蚂蚁颜色 */
static Color color;
/** 构造器
* @param id 蚂蚁编号
*/
public Ant(int id) {
this.id = id;
// currentEnvironment = e;
from = currentEnvironment.getMap().nest;
last = new Position(currentEnvironment.getMap().nest);
now = new Position(currentEnvironment.getMap().nest); //初始位置设为窝
to = currentEnvironment.getMap().food; //方向：窝->食物
forwardCounter = forwardOutTimes;
initDirection();
}
/** 绘制蚂蚁
* @param gc 设备环境
*/
public void draw(GC gc) {
//lastColor = gc.getForeground();
gc.setForeground(gc.getBackground());
gc.drawPoint(last.x, last.y);
gc.setForeground(color);
gc.drawPoint(now.x, now.y);
//gc.setForeground(old);
}
/** 蚂蚁行为 */
public void Proceed() {
// 位置判断
if(now.equals(to)) {
tour = optimizeTour(tour);
tourLength = tour.size();
currentEnvironment.endCycle(id);
return;
}
// 行走
move();
// 更新统计信息
tour.add(new Position(now));
tourLength++;
}
/** 重置蚂蚁，包括
* 路径，路径长度，起点，终点，当前位置
*/
public synchronized void reset() {
tourLength = 0;
tour.clear();
from = currentEnvironment.getMap().nest;
last.set(currentEnvironment.getMap().nest);
now.set(currentEnvironment.getMap().nest);
to = currentEnvironment.getMap().food;
}
public static PosList optimizeTour(PosList list) {
PosList opt = new PosList();
PosList inter = null;
int index = 0;
Position prev = list.get(index), curr; // prev 设为路径起始位置
while(index + optLength < list.size()) {
curr = list.get(index + optLength); // 优化目标位置，与prev距离optLength
inter = genLine(prev, curr);
if(inter.isEmpty()) { // 使用原路径
for(int i = 0; i < optLength; i++) {
opt.add(new Position(list.get(index++)));
}
} else { // 使用优化路径
PosListIterator iter = inter.iterator();
while(iter.hasNext()) {
opt.add(new Position(iter.next()));
}
index += optLength;
}
prev = list.get(index);
}
if(index < list.size()) {
inter = genLine(list.get(index), list.get(list.size() - 1));
if(inter.isEmpty()) {
while(index < list.size()) { // 最后剩余的不足optLength部分
opt.add(new Position(list.get(index++)));
}
} else {
PosListIterator iter = inter.iterator();
while(iter.hasNext()) {
opt.add(new Position(iter.next()));
}
opt.add(new Position(list.get(list.size() - 1)));
index = list.size();
}
}
return opt;
}
/** 蚂蚁移动（单步） */
private void move() {
boolean finished = false;
if(!lookingForward && rand.nextDouble() > pExplore) {
Position next = new Position(now), temp;
Pheromone pt, ph;
PosList avail = new PosList(); // 可行走的位置
// 查找所有可行走位置
for(int xx = now.x - 1; xx if(xx < 0 || xx >= Map.WIDTH) continue;
for(int yy = now.y - 1; yy if(yy < 0 || yy >= Map.HEIGHT) continue;
if(currentEnvironment.getMap().grid[xx][yy] != Map.BLOCKED)
avail.add(new Position(xx, yy));
}
}
avail.remove(now);
avail.remove(last);
last.set(now);
// 在可行走位置中寻找最吸引者
PosListIterator iter = avail.iterator();
while(iter.hasNext()) {
temp = iter.next();
pt = currentEnvironment.pheAt(temp);
ph = currentEnvironment.pheAt(next);
if(pt.get() > ph.get()) next = temp;
}
if(!next.equals(now)) {
now.set(next);
finished = true;
}
}
if(!finished) {
int dx = 1, dy = 0, temp = 0;
boolean done = false;
if(!lookingForward && rand.nextDouble() < pLookForward) lookForward();
else if(!lookingForward && rand.nextDouble() < pDisturb) disturb();
if(lookingForward && --forwardCounter == 0) {
lookingForward = false;
forwardCounter = forwardOutTimes;
}
while(!done) {
if(d > 0) d += incrE;
else {
d += incrNE;
dy = 1;
}
if(section > 3) {temp = dx; dx = dy; dy = temp; temp = section - 4;}
else temp = section;
switch(temp) {
case 0: break;
case 1: dx *= -1; break;
case 2: dy *= -1; break;
case 3: dx *= -1; dy *= -1; break;
}
now.dx(dx);
now.dy(dy);
if(passable()) {
last.set(now);
done = true;
} else {
now.set(last);
initDirection();
}
}
}
}
/** 随机选择方向 */
private void initDirection() {
section = rand.nextInt(8);
slope = rand.nextDouble();
d = (int)(100 * (1 - 2 * slope));
incrE = (int)(-200 * slope);
incrNE = (int)(200 * (1 - slope));
}
/** 前向参考 */
private void lookForward() {
lookingForward = true;
if(minTourLength == currentEnvironment.initLength) return;
int sec = 0; // 象限区域
// 向前查找长度
int index = tourLength + forwardMinLength + rand.nextInt(forwardMaxLength - forwardMinLength);
if(index >= minTourLength) index = minTourLength - 1;
Position p = minTour.get(index); // 已知最短路径前方位置
int dx = p.x - now.x;
int dy = p.y - now.y;
if(dx < 0) {
sec++;
dx = Math.abs(dx);
}
if(dy < 0) {
sec += 2;
dy = Math.abs(dy);
}
if(dx < dy) {
sec += 4;
int temp = dx;
dx = dy; dy = temp;
}
d = dx - 2 * dy;
incrE = -2 * dy;
incrNE = 2 * (dx - dy);
}
/** 可通过性判断 */
private boolean passable() {
boolean t = !now.equals(last) && now.x >= 0 && now.x < Map.WIDTH && now.y >= 0 && now.y < Map.HEIGHT && currentEnvironment.terranAt(now) != Map.BLOCKED;
return t;
}
/** 随机扰动 */
private void disturb() {
slope += -1 * rand.nextInt(2) * rand.nextDouble() / 2;
if(slope > 1) slope = 1;
if(slope < 0) slope = 0;
d = (int)(100 * (1 - 2 * slope));
incrE = (int)(-200 * slope);
incrNE = (int)(200 * (1 - slope));
}
/** 生成直线路径 */
private static PosList genLine(Position from, Position to) {
int dx = to.x - from.x;
int dy = to.y - from.y;
int temp; // 用于坐标交换
int sec = 0;
int d, incrE, incrNE;
Position t = new Position(from);
PosList list = new PosList();
// 区域判断
if(dx < 0) {
sec++;
dx = Math.abs(dx);
}
if(dy < 0) {
sec += 2;
dy = Math.abs(dy);
}
if(dx < dy) {
sec += 4;
temp = dx;
dx = dy; dy = temp;
}
// 计算增量
d = dx - 2 * dy;
incrE = -2 * dy;
incrNE = 2 * (dx - dy);
// 判断障碍
while(!t.equals(to)) {
if(currentEnvironment.terranAt(t) == Map.BLOCKED) {
list.clear();
break;
}
list.add(new Position(t));
if(d > 0) {
d += incrE;
dy = 0;
}
else {
d += incrNE;
dy = 1;
}
dx = 1;
// 对称变换
if(sec > 3) {temp = dx; dx = dy; dy = temp;}
switch(sec - 4) {
case 0: break;
case 1: dx *= -1; break;
case 2: dy *= -1; break;
case 3: dx *= -1; dy *= -1; break;
}
t.dx(dx);
t.dy(dy);
}
return list;
}
}
