Ant Control Programm Compiler
Site navigation
Team and strategy
Ant control language and compiler
Compiler
Our compiler is written in Java, translating ACP (Ant Control
Programs) to ANT assembler code. The source is about 3kloc.
Download
You may download a distribution archive with the our tools source code, or browse the compiler API documentaion online.
SVN Repository
You can have a look at the KaNT's team
repository, or check out the latest release using an subversion client (username
anonymous, empty password).
svn --username anonymous --password '' co http://svn.ipd.uka.de/repos/hauma/haui/trunk/icfp2004/
Ant Control Language
The Program
{
statement |
definition
}
Basic statements
move;
pick;
drop;
turn [Left|Right];
mark <n>;
unmark <n>;
Control flow statements
Each statement can be labeled:
label: statement;
Unconditional goto, and if statement:
goto label;
if (expression) { statements } else { statements };
Block-local variables
Variable definition:
{
var name;
statements
}
Variable Assignment:
name = expression;
Expresions
condition[direction]
variable
true
false
!expresion
expresion && expresion
expresion || expresion
Where the basic conditions are defined as follows:
Home
Food
Rock
Marker0
Marker1
Marker2
Marker3
Marker4
Marker5
Friend
FriendWithFood
Foe
FoeHome
FoeMarker
FoeWithFood
There are two special conditions that can be evaluated directly after
a move or pick statement respectively:
HitWall
FoundFood
The following directions can be given:
Here
Ahead
Left
Right
LeftAhead
RightAhead
Procedures
Procedure definition (of cause, no recursion!):
proc name(var param, ...) {
...
};
Procedure call:
name(expression, ...);
Learning by example
You may browse through the compiler test cases directly in the SVN
repository (empty password), or analyse our finalist ant in source
code below.
The ACP source code
/*
* ANT Simulation Programm
*
* ----------------------------------------------------------------------
*
* (c) by the ICFP 2004 Team "KaNT"
*
* Jens Hauke
* Thomas Moschny
* Bernhard Haumacher
* Bjoern Hartmann
*
* ----------------------------------------------------------------------
*
* This is free software (GPL).
*
* $Rev: 1551 $
* $Date: 2004-06-05 22:56:24 +0200 (Sat, 05 Jun 2004) $
*
*/
/* Idea of this ant:
* - mark all cells with a distance to home (modulo 3)
* in markers 0, 1, 2 (and 3 for fast access)
* - if found food go home shortest way and leave a trace (mark 4)
* - if found trace (and have no food) follow trace direction
* away from home (and delete trace sometimes.
* with mark 0 and mark 1 (called near home)
* - mark all cells with direct connection to near home
* with mark 0 and mark 2 (called far home)
* *jh*
*/
{
/*
* Marker: 0,1,2 for distance,
* 3 for distance is set/unset
* 4 for food trace
*/
var hasfood;
mark 0; mark 3; // Mark my home
killer();
turn Left;
turn Left;
turn Left;
killer();
start_wait:
if (Friend[Ahead]) {
turn Left;
goto start_wait;
};
/* color1 marking:*/
mark_with_1_loop:
move; if (HitWall) goto hit_wall_while_marking;
mark 1; mark 3;
if (Food[Here]) {
pick; set hasfood;
goto fast_go_home_with_food;
};
call find_marker_leftside();
/* Now: In front no marker, left one marker */
if (Marker0[LeftAhead]) {
// continue writing 1
goto mark_with_1_loop;
} else {
goto mark_with_2_loop;
};
/* ----------------------------------------- */
/* color2 marking:*/
mark_with_2_loop:
move; if (HitWall) goto hit_wall_while_marking;
mark 2; mark 3;
if (Food[Here]) {
pick; set hasfood;
goto fast_go_home_with_food;
};
call find_marker_leftside();
/* Now: In front no marker, left one marker or wall */
if (Marker1[LeftAhead]) {
// continue writing 2
goto mark_with_2_loop;
} else {
goto mark_with_0_loop;
};
/* ----------------------------------------- */
/* color0 marking:*/
mark_with_0_loop:
move; if (HitWall) goto hit_wall_while_marking;
mark 0; mark 3;
if (Food[Here]) {
pick; set hasfood;
goto fast_go_home_with_food;
};
call find_marker_leftside();
/* Now: In front no marker, left one marker */
if (Marker2[LeftAhead]) {
// continue writing 2
goto mark_with_0_loop;
} else {
goto mark_with_1_loop;
};
/* ----------------------------------------- */
hit_wall_while_marking:
{};
goto random_walk_for_food;
/* ----------------------------------------- */
fast_go_home_with_food:
// ToDo: go_home ant leave a trace
goto fast_go_home;
/* ----------------------------------------- */
fast_go_home:
if (Marker0[Here]) {
goto search2;
} else if (Marker1[Here]) {
goto search0;
} else if (Marker2[Here]) {
goto search1;
} else {
goto random_walk_to_home;
};
/* ---- */
_search2:
move;
if (hasfood) mark 4;
search2:
if (Home[Here]) goto i_am_at_home;
if (Marker2[Ahead]) {
goto _search1;
} else if (Marker2[LeftAhead]) {
turn Left; goto _search1;
} else if (Marker2[RightAhead]) {
turn Right; goto _search1;
} else {
turn Left; goto search2;
};
_search1:
move;
if (hasfood) mark 4;
search1:
if (Home[Here]) goto i_am_at_home;
if (Marker1[Ahead]) {
goto _search0;
} else if (Marker1[LeftAhead]) {
turn Left; goto _search0;
} else if (Marker1[RightAhead]) {
turn Right; goto _search0;
} else {
turn Left; goto search1;
};
_search0:
move;
if (hasfood) mark 4;
search0:
if (Home[Here]) goto i_am_at_home;
if (Marker0[Ahead]) {
goto _search2;
} else if (Marker0[LeftAhead]) {
turn Left; goto _search2;
} else if (Marker0[RightAhead]) {
turn Right; goto _search2;
} else {
turn Left; goto search0;
};
/*---------*/
i_am_at_home:
/* go a little in */
if (Home[Ahead]) {
move;
if (Home[Ahead]) {
move;
if (Home[Ahead]) {
move;
};
};
};
drop; unset hasfood;
/* ToDo: follow traces back to food! */
goto random_walk_for_food;
/* ----------------------------------------- */
/* assume: standing on a marked field, ahead is a
unmarked field */
continue_mark_from_ahead:
if (Marker0[Here]) {
goto mark_with_1_loop;
} else if (Marker1[Here]) {
goto mark_with_2_loop;
} else if (Marker2[Here]) {
goto mark_with_0_loop;
} else goto random_walk_for_food;
/* ----------------------------------------- */
random_walk_for_food:
/*
Random walk until food, than go home!
*/
{};
goAway:
if ( Food[LeftAhead] && (!Home[LeftAhead])) {
turn Left;
goto goMoveAndPickGoHome;
} else if ( Food[RightAhead] && (!Home[RightAhead])) {
turn Right;
goto goMoveAndPickGoHome;
} else if (Food[Ahead] && (!Home[Ahead])) {
goto goMoveAndPickGoHome;
} else {
if ( random(20) ) {
call turn_random_50_50();
};
if ((!Marker3[Ahead]) && (!Rock[Ahead]))
goto continue_mark_from_ahead;
move;
if ( HitWall ) {
turn Left;
} else {
if (Marker4[Here]) goto follow_marker_to_food;
};
goto goAway;
};
/* ---- */
goMoveAndPickGoHome:
move;
pick; set hasfood;
goto fast_go_home;
/* ----------------------------------------- */
follow_marker_to_food:
/* sit on top of food trace. go in direction away from
home, but still staying on top of trace */
follow_marker_to_food_one_step();
follow_marker_to_food_one_step();
follow_marker_to_food_one_step();
follow_marker_to_food_one_step();
follow_marker_to_food_one_step();
follow_marker_to_food_one_step();
/* Lost trace..... make random walk */
goto random_walk_for_food;
/* ----------------------------------------- */
proc follow_marker_to_food_one_step() {
/* ToDo: optimize this by expanding (eg.
(Marker0[Here] sometimes known without test!) */
if (Marker4[Ahead] &&
((Marker0[Here] && Marker1[Ahead]) ||
(Marker1[Here] && Marker2[Ahead]) ||
(Marker2[Here] && Marker0[Ahead]) ||
(!Marker3[Ahead]))) {
move;
if (HitWall) {
turn Left;
move;
if (! HitWall) {
turn Right;
};
} else {
if (random(3/* ToDo: Adjust Value to optimum! Done.
lower is better, but 3 is the best against
powerant and maybe others?
*/)) unmark 4;
goto follow_marker_to_food; /* ugly exit from proc */
}
} else {
turn Left;
}
};
/* ----------------------------------------- */
random_walk_to_home:
/*
Random walk until reach a mark0 than go home!
*/
{};
goAway_home:
if (Marker0[LeftAhead]) {
turn Left;
move;
goto fast_go_home;
} else if (Marker0[RightAhead]) {
turn Right;
move;
goto fast_go_home;
} else {
if ( random(10/* ToDo: Adjust Value to optimum! */) ) {
call turn_random_50_50();
};
move;
if ( HitWall ) turn Left;
goto goAway_home;
};
/* ----------------------------------------- */
/* ---Functions ---------------------------- */
/* ----------------------------------------- */
/* ----------------------------------------- */
/* ----------------------------------------- */
// endless loops
/*
proc find_marker_leftside() {
if (Marker3[Ahead] || Rock[Ahead]) {
turn Right;
if (Marker3[Ahead] || Rock[Ahead]) {
turn Right;
if (Marker3[Ahead] || Rock[Ahead]) {
goto fast_go_home;
};
};
} else if (!(Marker3[LeftAhead] || Rock[LeftAhead])) {
turn Left;
if (!(Marker3[LeftAhead] || Rock[LeftAhead])) {
turn Left;
if (!(Marker3[LeftAhead] || Rock[LeftAhead])) {
goto fast_go_home;
};
};
};
};
*/
proc find_marker_leftside() {
if (Marker3[Ahead]) {
turn Right;
if (Marker3[Ahead]) {
turn Right;
if (Marker3[Ahead] || Rock[Ahead]) {
goto fast_go_home;
};
};
} else if (!(Marker3[LeftAhead])) {
turn Left;
if (!(Marker3[LeftAhead] )) {
turn Left;
if (!(Marker3[LeftAhead])) {
goto fast_go_home;
};
};
};
};
proc turn_random_50_50() {
if (random(2)) {
turn Left;
} else {
turn Right;
};
};
todo:
// turn Right;
unmark 5;
// turn Right;
mark 5;
goto todo;
abort:
// turn Left;
mark 5;
goto abort;
proc killer() { /* start of killer block.
must be called in sync on startup!!!!!
seams to be the best, to use 2 killers
and one move_force after building (see xx5x)
*/
if ((!Home[RightAhead]) && (!Home[LeftAhead])) {
/* Leader */
mark 5;
drop;
unmark 5;
turn Left;
turn Left;
turn Left;
move_force();
move_force();
turn Right;
turn Right;
turn Right;
stay_in_fall:
/* maybe go somewhere? (all ants have same orientation) */
{};
move_force(); // <--- xx5x
/* final position */
stay_in_fall_loop:
turn Left;
goto stay_in_fall_loop;
} else {
drop;
if (Marker5[LeftAhead] || Marker5[RightAhead]) {
/* second */
mark 4;
drop;
unmark 4;
goto stay_in_fall;
} else {
/* maybe need to wait */
drop;
if (Marker4[Ahead]) {
/* third */
goto stay_in_fall;
}
};
};
}; /* end of killer block*/
proc move_force() {
_move_force_loop:
move; if (HitWall) goto _move_force_loop;
};
}
The generated ANT assembler code
Mark 0 1
Mark 3 2
Sense RightAhead 3 299 Home
Drop 4
Sense LeftAhead 5 10 Marker 5
Mark 4 6
Drop 7
Unmark 4 8
Move 9 8
Turn Left 9
Sense RightAhead 5 11 Marker 5
Drop 12
Sense Ahead 8 13 Marker 4
Turn Left 14
Turn Left 15
Turn Left 16
Sense RightAhead 17 287 Home
Drop 18
Sense LeftAhead 19 24 Marker 5
Mark 4 20
Drop 21
Unmark 4 22
Move 23 22
Turn Left 23
Sense RightAhead 19 25 Marker 5
Drop 26
Sense Ahead 22 27 Marker 4
Sense Ahead 28 29 Friend
Turn Left 27
Move 30 43
Mark 1 31
Mark 3 32
Sense Here 33 275 Food
PickUp 34 34
Sense Here 35 261 Marker 0
Sense Here 36 235 Home
Sense Ahead 37 42 Home
Move 38 38
Sense Ahead 39 42 Home
Move 40 40
Sense Ahead 41 42 Home
Move 42 42
Drop 43
Sense LeftAhead 44 45 Food
Sense LeftAhead 45 234 Home
Sense RightAhead 46 47 Food
Sense RightAhead 47 233 Home
Sense Ahead 48 49 Food
Sense Ahead 49 231 Home
Flip 20 50 52
Flip 2 51 230
Turn Left 52
Sense Ahead 53 146 Marker 3
Move 54 145
Sense Here 55 43 Marker 4
Sense Ahead 56 144 Marker 4
Sense Here 57 139 Marker 0
Sense Ahead 58 139 Marker 1
Move 59 61
Flip 3 60 55
Unmark 4 55
Turn Left 62
Move 63 64
Turn Right 64
Sense Ahead 65 138 Marker 4
Sense Here 66 133 Marker 0
Sense Ahead 67 133 Marker 1
Move 68 70
Flip 3 69 55
Unmark 4 55
Turn Left 71
Move 72 73
Turn Right 73
Sense Ahead 74 132 Marker 4
Sense Here 75 127 Marker 0
Sense Ahead 76 127 Marker 1
Move 77 79
Flip 3 78 55
Unmark 4 55
Turn Left 80
Move 81 82
Turn Right 82
Sense Ahead 83 126 Marker 4
Sense Here 84 121 Marker 0
Sense Ahead 85 121 Marker 1
Move 86 88
Flip 3 87 55
Unmark 4 55
Turn Left 89
Move 90 91
Turn Right 91
Sense Ahead 92 120 Marker 4
Sense Here 93 115 Marker 0
Sense Ahead 94 115 Marker 1
Move 95 97
Flip 3 96 55
Unmark 4 55
Turn Left 98
Move 99 100
Turn Right 100
Sense Ahead 101 114 Marker 4
Sense Here 102 109 Marker 0
Sense Ahead 103 109 Marker 1
Move 104 106
Flip 3 105 55
Unmark 4 55
Turn Left 107
Move 108 43
Turn Right 43
Sense Here 110 111 Marker 1
Sense Ahead 103 111 Marker 2
Sense Here 112 113 Marker 2
Sense Ahead 103 113 Marker 0
Sense Ahead 114 103 Marker 3
Turn Left 43
Sense Here 116 117 Marker 1
Sense Ahead 94 117 Marker 2
Sense Here 118 119 Marker 2
Sense Ahead 94 119 Marker 0
Sense Ahead 120 94 Marker 3
Turn Left 100
Sense Here 122 123 Marker 1
Sense Ahead 85 123 Marker 2
Sense Here 124 125 Marker 2
Sense Ahead 85 125 Marker 0
Sense Ahead 126 85 Marker 3
Turn Left 91
Sense Here 128 129 Marker 1
Sense Ahead 76 129 Marker 2
Sense Here 130 131 Marker 2
Sense Ahead 76 131 Marker 0
Sense Ahead 132 76 Marker 3
Turn Left 82
Sense Here 134 135 Marker 1
Sense Ahead 67 135 Marker 2
Sense Here 136 137 Marker 2
Sense Ahead 67 137 Marker 0
Sense Ahead 138 67 Marker 3
Turn Left 73
Sense Here 140 141 Marker 1
Sense Ahead 58 141 Marker 2
Sense Here 142 143 Marker 2
Sense Ahead 58 143 Marker 0
Sense Ahead 144 58 Marker 3
Turn Left 64
Turn Left 43
Sense Ahead 53 147 Rock
Sense Here 29 148 Marker 0
Sense Here 149 229 Marker 1
Move 150 43
Mark 2 151
Mark 3 152
Sense Here 153 154 Food
PickUp 34 34
Sense Ahead 155 224 Marker 3
Turn Right 156
Sense Ahead 157 206 Marker 3
Turn Right 158
Sense Ahead 159 205 Marker 3
Sense Here 160 191 Marker 0
Sense Here 161 168 Home
Sense Ahead 162 167 Home
Move 163 163
Sense Ahead 164 167 Home
Move 165 165
Sense Ahead 166 167 Home
Move 167 167
Drop 43
Sense Ahead 169 186 Marker 2
Move 170 170
Sense Here 161 171 Home
Sense Ahead 172 181 Marker 1
Move 173 173
Sense Here 161 174 Home
Sense Ahead 175 176 Marker 0
Move 160 160
Sense LeftAhead 177 178 Marker 0
Turn Left 175
Sense RightAhead 179 180 Marker 0
Turn Right 175
Turn Left 173
Sense LeftAhead 182 183 Marker 1
Turn Left 172
Sense RightAhead 184 185 Marker 1
Turn Right 172
Turn Left 170
Sense LeftAhead 187 188 Marker 2
Turn Left 169
Sense RightAhead 189 190 Marker 2
Turn Right 169
Turn Left 160
Sense Here 173 192 Marker 1
Sense Here 170 193 Marker 2
Sense LeftAhead 194 196 Marker 0
Turn Left 195
Move 159 159
Sense RightAhead 197 199 Marker 0
Turn Right 198
Move 159 159
Flip 10 200 202
Flip 2 201 204
Turn Left 202
Move 193 203
Turn Left 193
Turn Right 202
Sense Ahead 159 206 Rock
Sense LeftAhead 149 207 Marker 1
Move 208 43
Mark 0 209
Mark 3 210
Sense Here 211 212 Food
PickUp 34 34
Sense Ahead 213 219 Marker 3
Turn Right 214
Sense Ahead 215 218 Marker 3
Turn Right 216
Sense Ahead 159 217 Marker 3
Sense Ahead 159 218 Rock
Sense LeftAhead 207 29 Marker 2
Sense LeftAhead 218 220 Marker 3
Turn Left 221
Sense LeftAhead 218 222 Marker 3
Turn Left 223
Sense LeftAhead 218 159 Marker 3
Sense LeftAhead 206 225 Marker 3
Turn Left 226
Sense LeftAhead 206 227 Marker 3
Turn Left 228
Sense LeftAhead 206 159 Marker 3
Sense Here 207 43 Marker 2
Turn Right 52
Move 232 232
PickUp 34 34
Turn Right 231
Turn Left 231
Sense Ahead 236 256 Marker 2
Move 237 237
Mark 4 238
Sense Here 36 239 Home
Sense Ahead 240 251 Marker 1
Move 241 241
Mark 4 242
Sense Here 36 243 Home
Sense Ahead 244 246 Marker 0
Move 245 245
Mark 4 35
Sense LeftAhead 247 248 Marker 0
Turn Left 244
Sense RightAhead 249 250 Marker 0
Turn Right 244
Turn Left 242
Sense LeftAhead 252 253 Marker 1
Turn Left 240
Sense RightAhead 254 255 Marker 1
Turn Right 240
Turn Left 238
Sense LeftAhead 257 258 Marker 2
Turn Left 236
Sense RightAhead 259 260 Marker 2
Turn Right 236
Turn Left 35
Sense Here 242 262 Marker 1
Sense Here 238 263 Marker 2
Sense LeftAhead 264 266 Marker 0
Turn Left 265
Move 34 34
Sense RightAhead 267 269 Marker 0
Turn Right 268
Move 34 34
Flip 10 270 272
Flip 2 271 274
Turn Left 272
Move 263 273
Turn Left 263
Turn Right 272
Sense Ahead 276 282 Marker 3
Turn Right 277
Sense Ahead 278 281 Marker 3
Turn Right 279
Sense Ahead 159 280 Marker 3
Sense Ahead 159 281 Rock
Sense LeftAhead 29 149 Marker 0
Sense LeftAhead 281 283 Marker 3
Turn Left 284
Sense LeftAhead 281 285 Marker 3
Turn Left 286
Sense LeftAhead 281 159 Marker 3
Sense LeftAhead 17 288 Home
Mark 5 289
Drop 290
Unmark 5 291
Turn Left 292
Turn Left 293
Turn Left 294
Move 295 294
Move 296 295
Turn Right 297
Turn Right 298
Turn Right 22
Sense LeftAhead 3 300 Home
Mark 5 301
Drop 302
Unmark 5 303
Turn Left 304
Turn Left 305
Turn Left 306
Move 307 306
Move 308 307
Turn Right 309
Turn Right 310
Turn Right 8
Page design: Bernhard Haumacher
Last modified: Tue Jun 8 17:47:36 CEST 2004