David Finch's solution:
I just pasted the map into my solver and updated the constants.
//Written by David Finch, dtfinch@charter.net or david@mytsoftware.com
#include <stdio.h>
#include <stdlib.h>
#define Width 100
#define Height 75
#define PWidth (Width*10)
#define PHeight (Height*10)
#define NumPoints 162544 // # of reachable x,y positions, or the most we want to look at
//too lazy to write a loader, so here's the map
//The dashes are to exclude areas of the map that'll waste time and memory.
char map[Height][Width+1]={
" \000",
" \000",
" \000",
" # \000",
" \000",
" # O ### # # \000",
" # ### ##### # # ## # # # \000",
" # #### ### # ## # ### # ###### # \000",
" ### # # #### ###### #### ### # # # ##### #### ## # # ## # \000",
" # # # # # ############# ## ## # ## # # ## # ## ## # # ##\000",
" # # ## ################ # # # ## # #### # # ##### ## ## \000",
" # ## # ##################### ### ## ## ## ## # # ##### # # ## #\000",
" ## # # # # ############################# #### #### ### ## #### ### ### # # #\000",
" # # # ######################## ## #### ## ###### ####### ## ## ## #### #\000",
"# # # ## # # ## ######################## #### # #### # ### # # ####### # ## # ######\000",
"# ##### ## ## ######################## ###### # ## # # # # # ## # # ####### \000",
" # # # ####################### ######## # # # ##### # # # # # ########\000",
" # # # ########################### ####### ### # ####### #### #### ## # ##### \000",
" # # ## # # ############################## ### ### # ### ######\000",
" ## # ### # # # # ########################## # #### ## ## ## ## # ###### \000",
" # ### # # # ########################## # # # # # # ## # ### ## # # ###\000",
" # #### # # ## ######### ############# # ##### ## # # # ### ## #####\000",
" # ### # # ## # ###### ## # # # # # # # # ##### ######\000",
"# ## # # # # # ######## #### # ## ### #### ### # #####\000",
"## ### ## # #### ## ############## # ## # # ######## # ## #####\000",
" ## # ###### ######## # ################ # # ## ### ### # # # ####\000",
" ### # # ######## ####### ## ## ########### # # # # ### ## # #### #####\000",
" # ### # ###### ######### # # ######### # # ### # #### ## # ###\000",
" ## #### ####### # # ###### # ########## # # # # ### ### # ## ## # ##\000",
" ##### # ################ # ## ##### #### ## # # # # ########## # # ## \000",
" # # ## ############################ # # # ### # ############ ### # \000",
" # ### ############### ############ # ## # # # ########### \000",
" ## # ### # # ########################## ## ################# # \000",
" ############## ############## ########### #### # # #### # # ############# ### \000",
"# ## # ####### ########## ####### # ## ## ### ## ## ### ########## # # #\000",
" # ######## # ########## # #### ## # #### # ## # ## ###### # ### # \000",
" ## ######## ## ## ###### #### ## ### ## # ## ##### # # ######## # ### #\000",
" # ############## ######### # # # # # # ## ####### # # ###### # ### ## # \000",
" # ############### ###### # # # #### # #### ######## # # ## # # # ## \000",
" # ################ ####### # # # # ##### ####### ### ### ## ## ##### \000",
" ################ ###### ## # # ## ########## ## #### ## # ## ##### \000",
"# # ############# ####### ### ## # # ##### # ## ## ## ## # # ### # \000",
" ## ##### # ######## # #### # ######## ####### # # ### ## \000",
" # # # # ##### # # # ## # # ###### ####### ## ## # # # # # \000",
" # ###### #### ### # ## ########## # ### ####### ## ##### # # #### \000",
"# ## # # ### ## ## # # # ############ #### ### ######### # # # ##\000",
"## # # # #### #### ## # ############# ### # # # ### # ## # ## \000",
"# # # ## # ## # ## # # ############# ## ## # #### # ### ### # ###\000",
" # # # ## ### # ## ####### #################### #### ########## ######## # #\000",
"## # ### # # ## ###### ### ################### #### ### ### # ##### #\000",
" ## # # ## # # # ## # ### ################ # ####### # # ##### ###### \000",
"# # # # ### # # # ###### # #################### ############ ## ## ## \000",
" # # # # # # # ## ######### # ################################ # # ##########\000",
"# # # # ## # ## ##### ###### # ################## ################ #### #######\000",
"## # # ####### ## ###### ######## ######## ######################## #### ### ## # \000",
" # ####### ## # # ############### ################################## ###### ## # #\000",
" # # ####### # ## ####### ####### ### ######################## ################## \000",
" # ####### ################## # ## ############################### ##### ####### ##\000",
" # # # ## ## ################## # # ### ################################### ## ### \000",
" ### # # # ### ##################### ## ######################################### # # # # \000",
"# # ####### #################### ### ############## ## ######################## ## ## ##\000",
" # ######################### #### ##### ### ## ############### ############ # ## ##\000",
" ## # ######################### # ##### # # ## ## # # #################### ### #\000",
" ## # ############### # # ## # # ##### #### # ## # ### ######################### \000",
" # # # ############## # ## # # ### # ######### ###### # ### ###### ### ## # # # #\000",
" # # ########## # # ############ ####### # ## ## ############ ### # # \000",
" ## # ## ####### ### # # ### # # ######## ################### ## # # ##\000",
"# # ####### ### # # # # # # ##### ### ## ###### ## ######## ### # ## \000",
"# ###### ### # # # # # # # # ## # ### ##### ### ##### ### # ## # \000",
"# # # ### # # # # #### # ## # ## #### ## ### # ####### # # ### \000",
" ### #### # # ## # # ## #### ## ## # # ######## # ###### ## # # ###### #\000",
" ## # ## # # # ### #### # ### ## ## ## ### ### ### # ### ###### \000",
" # # # ## # # # + ## # # ## ## # ## ###### # #### # ### ## ####### ######\000",
" # # # # ## # #### ## # # # ### # ## ## # ### ## ### # ###### \000",
" ## ### # # # ## # ## # # # ## # ### # ## # ## # # # ######\000"
};
/*
A node only needs to store the address of the best source and if it was visited.
Address format: 32 bit
visited:1 - When searching for shortest path by # of steps, we only need to track visited vs unvisited.
map:1 - Which map, to or from.
xy:20
dx:5
dy:5
*/
#define Visited ((unsigned int)1<<31)
#define pack(v,m,x,y,dx,dy) (((unsigned int)(v)<<31)|((m)<<30)|(indexes[x][y]<<10)|(((dx)+16)<<5)|((dy)+16))
#define unpackv(a) (((a)>>31)&1)
#define unpackm(a) (((a)>>30)&1)
#define unpackx(a) RevX[((a)>>10)&1048575]
#define unpacky(a) RevY[((a)>>10)&1048575]
#define unpackdx(a) ((((a)>>5)&31)-16)
#define unpackdy(a) (((a)&31)-16)
#define ListSize 5000000
typedef unsigned int Address;
typedef struct {
int x;
int y;
int dx;
int dy;
int map;
int visited;
} SAddress;
typedef struct {
Address points[ListSize];
unsigned short int fuel[ListSize];
int length;
} List;
Address world[2][NumPoints][21][21];
#define source(a) world[unpackm(a)][indexes[unpackx(a)][unpacky(a)]][unpackdx(a)+10][unpackdy(a)+10]
List lists[2];
List *srcL=&lists[0];
List *destL=&lists[1];
#define pop() (srcL->points[--srcL->length])
#define empty() (srcL->length==0)
void push(Address a, int fuel) {
destL->fuel[destL->length]=fuel;
destL->points[destL->length++]=a;
}
#define NoAddress ((Address)0xffffffff)
#define PBlocked 1
#define PStart 2
#define PEnd 4
typedef char PState;
int spaces=0;
int indexes[PWidth][PHeight];
PState PixMap[PWidth][PHeight];
int RevX[NumPoints];
int RevY[NumPoints];
Address spack(SAddress *a) {
return pack(a->visited,a->map,a->x,a->y,a->dx,a->dy);
}
void Blot(int x,int y) {
map[y/10][x/10]='*';
}
void PrintMap() {
int i;
printf("\n");
for(i=0;i<Height;i++) {
printf("%s\n",map[i]);
}
}
void sunpack(Address a, SAddress *r) {
r->x=unpackx(a);
r->y=unpacky(a);
r->dx=unpackdx(a);
r->dy=unpackdy(a);
r->map=unpackm(a);
r->visited=unpackv(a);
}
PState GetMapStatePoint(int x, int y) {
x=x/10;
y=y/10;
if(x>=80 && x<100) return PBlocked; //some culling
switch(map[y][x]) {
case ' ':
return 0;
case 'O':
return PStart;
case '+':
return PEnd;
}
return PBlocked;
}
PState GetMapStateSlow(int x, int y) {
return GetMapStatePoint(x,y)
| GetMapStatePoint(x+9,y)
| GetMapStatePoint(x,y+9)
| GetMapStatePoint(x+9,y+9);
}
PState GetMapStateFast(int x, int y) {
if(x<0 || y<0 || x>=PWidth || y>=PHeight) return PBlocked;
return PixMap[x][y];
}
#define isWin(a) (unpackm(a)==1&&(PixMap[unpackx(a)][unpacky(a)]&PStart))
Address CalcDest(Address src, int left, int up, int right) {
SAddress d;
char s;
sunpack(src,&d);
if(d.dx>10 && right) return NoAddress;
if(d.dx<-10 && left) return NoAddress;
if(left) d.dx-=2;
if(right) d.dx+=2;
if(up) d.dy-=1; else d.dy+=1;
if(d.dx>10) d.dx=10;
if(d.dx<-10) d.dx=-10;
if(d.dy>10) d.dy=10;
if(d.dy<-10) d.dy=-10;
while((s=GetMapStateFast(d.x+d.dx,d.y+d.dy))&PBlocked) {
d.dx/=2;
d.dy/=2;
}
d.x+=d.dx;
d.y+=d.dy;
if((s&PEnd)&&d.map==0) d.map=1;
// printf(" [%d %d %d %d %d]",d.map,d.x,d.y,d.dx,d.dy);
return spack(&d);
}
void TracePath(Address dest) {
Address src;
char buffer[2000];
char *s=buffer+1900;
*s=0;
do {
src=source(dest);
if((dest|Visited)==(CalcDest(src,0,0,0)|Visited)) *--s='0';
else if((dest|Visited)==(CalcDest(src,1,0,0)|Visited)) *--s='1';
else if((dest|Visited)==(CalcDest(src,0,1,0)|Visited)) *--s='2';
else if((dest|Visited)==(CalcDest(src,0,0,1)|Visited)) *--s='4';
else if((dest|Visited)==(CalcDest(src,1,1,0)|Visited)) *--s='3';
else if((dest|Visited)==(CalcDest(src,0,1,1)|Visited)) *--s='6';
else *--s='?';
if(s<=buffer) {
printf("Error");
return;
}
dest=src;
} while(unpackx(src)!=280||unpacky(src)!=50||unpackm(src)!=0);
printf("\n%s\n",s);
}
void MoveAbsolute(Address src, Address dest, int fuel) {
if(dest!=NoAddress && unpackv(source(dest))==0) { //if destination hasn't been visited yet
source(dest)=src|Visited;
push(dest,fuel);
if(isWin(dest)) {
printf("Done\n");
TracePath(dest);
exit(0);
}
//printf("+");
//Blot(unpackx(dest),unpacky(dest));
}// else printf("-");
}
void SwapLists() {
List *temp;
temp=srcL;
srcL=destL;
destL=temp;
}
//I know this is horribly inefficient. I'm too lazy to sort.
void ProcessList() {
SwapLists();
destL->length=0;
int i,f;
int mf=10000,xf=0;
for(i=0;i<srcL->length;i++) {
int fuel=srcL->fuel[i];
if(fuel<mf) mf=fuel;
if(fuel>xf) xf=fuel;
}
xf+=2;
for(f=mf;f<=xf;f++) {
for(i=0;i<srcL->length;i++) {
Address src=srcL->points[i];
int fuel=srcL->fuel[i];
if(fuel==f) {
MoveAbsolute(src,CalcDest(src,0,0,0),f);
}
if(fuel+1==f) {
MoveAbsolute(src,CalcDest(src,1,0,0),f);
MoveAbsolute(src,CalcDest(src,0,1,0),f);
MoveAbsolute(src,CalcDest(src,0,0,1),f);
}
if(fuel+2==f) {
MoveAbsolute(src,CalcDest(src,1,1,0),f);
MoveAbsolute(src,CalcDest(src,0,1,1),f);
}
}
}
}
void FillPixMap() {
int x,y,j,k;
char s;
for(j=0;j<2048;j++) {
for(k=0;k<2048;k++) {
x=(j&0xaaaaaaaa)|(k&0x55555555); //this mixing should improve locality, to increase cache hits and reduce swap activity. I hope.
y=(j&0x55555555)|(k&0xaaaaaaaa);
if(x<PWidth && y<PHeight) {
PixMap[x][y]=s=GetMapStateSlow(x,y);
if((s & PBlocked)==0) {
RevX[spaces]=x;
RevY[spaces]=y;
indexes[x][y]=spaces++;
}
}
}
}
}
void ClearNodes() {
int i,j,k;
for(i=0;i<NumPoints;i++) {
for(j=0;j<21;j++) {
for(k=0;k<21;k++) {
world[0][i][j][k]=0;
world[1][i][j][k]=0;
}
}
}
}
int main(void) {
printf("started\n");
int steps=0;
FillPixMap();
printf("Spaces: %d\n",spaces);
// return;
ClearNodes();
push(pack(0,0,280,50,0,0),0); //Starting position
while(destL->length) {
printf("\n%d %d",++steps,destL->length);
ProcessList();
}
printf("\n");
PrintMap();
return 0;
}