maze

gistfile1.txt

package ca.deamon.dungeon;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class MazeGen {
	int w, h;
	byte[] region;
	List<int[]> eau = new ArrayList<int[]>();
	//0 = unexposed and undetermined
	//1 = exposed and undetermined
	//2 = empty space
	//3 = wall
	public MazeGen(int w, int h) {
		this.w = w;
		this.h = h;
		this.region = new byte[w*h];
		for(int i = 0; i < region.length; i++) {
			region[i] = 0;
		}

		System.out.println("start " + w + " " + h);
	}
	
	public void gen(int[] out, int sx, int sy, int[] end) {
		Random rand = new Random();
		carve(sx, sy);
		int branchrate = 0;
		while(eau.size() > 0) {
			double pos = rand.nextDouble();
			pos = Math.pow(pos, Math.pow(Math.E, -branchrate));
			int[] choice = eau.get((int) Math.floor(pos * eau.size()));
			if(check(choice[0], choice[1], true)) {
				carve(choice[0], choice[1]);
			} else {
				harden(choice[0], choice[1]);
			}
			eau.remove(choice);
			//System.out.println("end loop " + eau.size());
		}
		for(int i = 0; i < region.length; i++) {
			if(region[i] == 1) {
				region[i] = 3;
			}
			out[i] = region[i];
		}
		findFarthest(end, sx, sy);
	}
	
	public void findFarthest(int[] end, int sx, int sy) {
		int[] map = new int[w*h];
		for(int i = 0; i < map.length; i++) map[i] = Integer.MIN_VALUE;
		farthestStep(map, sx, sy, 0);
		int highest = 0;
		for(int y = 0; y < h; y++) {
			for(int x = 0; x < w; x++) {
				/*if(map[x + y * w] != Integer.MIN_VALUE) {
					System.out.printf("%3d ", map[x + y * w]);
				} else {
					System.out.print("    ");
				}*/
				if(map[x + y * w] > highest) {
					highest = map[x + y * w];
					end[0] = x;
					end[1] = y;
				}
			}
			//System.out.println();
		}
	}
	
	public void farthestStep(int[] map, int x, int y, int c) {
		map[x + y * w] = c;
		c++;
		if(x > 0) {
			if(region[(x-1) + y * w] == 2 && map[(x-1) + y * w] == Integer.MIN_VALUE) {
				farthestStep(map, x-1, y, c);
			}
		}
		if(x < w-1) {
			if(region[(x+1) + y * w] == 2 && map[(x+1) + y * w] == Integer.MIN_VALUE) {
				farthestStep(map, x+1, y, c);
			}
		}
		if(y > 0) {
			if(region[x + (y-1) * w] == 2 && map[x + (y-1) * w] == Integer.MIN_VALUE) {
				farthestStep(map, x, y-1, c);
			}
		}
		if(y < h-1) {
			if(region[x + (y+1) * w] == 2 && map[x + (y+1) * w] == Integer.MIN_VALUE) {
				farthestStep(map, x, y+1, c);
			}
		}
	}
	
	private void carve(int x, int y)  {
		//System.out.println("carve " + x + " " + y);
		List<int[]> extra = new ArrayList<int[]>();
		region[x + y * w] = 2;
		if(x > 0) {
			if(region[(x-1) + y * w] == 0) {
				region[(x-1) + y * w] = 1;
				extra.add(new int[]{x-1, y});
			}
		}
		if(x < w-1) {
			if(region[(x+1) + y * w] == 0) {
				region[(x+1) + y * w] = 1;
				extra.add(new int[]{x+1, y});
			}
		}
		if(y > 0) {
			if(region[x + (y-1) * w] == 0) {
				region[x + (y-1) * w] = 1;
				extra.add(new int[]{x, y-1});
			}
		}
		if(y < h-1) {
			if(region[x + (y+1) * w] == 0) {
				region[x + (y+1) * w] = 1;
				extra.add(new int[]{x, y+1});
			}
		}
		Collections.shuffle(extra);
		eau.addAll(extra);
	}
	
	private void harden(int x, int y) {
		//System.out.println("harden " + x + " " + y);
		region[x + y * w] = 3;
	}
	
	private boolean check(int x, int y, boolean nodiagonals) {

		//System.out.println("check " + x + " " + y);
	    int edgestate = 0;
	    if(x > 0) {
			if(region[(x-1) + y * w] == 2) {
				edgestate += 1;
			}
		}
		if(x < w-1) {
			if(region[(x+1) + y * w] == 2) {
				edgestate += 2;
			}
		}
		if(y > 0) {
			if(region[x + (y-1) * w] == 2) {
				edgestate += 4;
			}
		}
		if(y < h-1) {
			if(region[x + (y+1) * w] == 2) {
				edgestate += 8;
			}
		}
		
		if(nodiagonals) {
			if(edgestate == 1) {
				if(x < h-1) {
					if(y > 0) {
						if(region[(x + 1) + (y - 1) * w] == 2) {
							return false;
						}
					}
					if(y < h - 1) {
						if(region[(x + 1) + (y + 1) * w] == 2) {
							return false;
						}
					}
				}
				return true;
			}
			if(edgestate == 2) {
				if(x > 0) {
					if(y > 0) {
						if(region[(x - 1) + (y - 1) * w] == 2) {
							return false;
						}
					}
					if(y < h - 1) {
						if(region[(x - 1) + (y + 1) * w] == 2) {
							return false;
						}
					}
				}
				return true;
			}
			if(edgestate == 4) {
				if(y < h-1) {
					if(x > 0) {
						if(region[(x - 1) + (y + 1) * w] == 2) {
							return false;
						}
					}
					if(x < w - 1) {
						if(region[(x + 1) + (y + 1) * w] == 2) {
							return false;
						}
					}
				}
				return true;
			}
			if(edgestate == 8) {
				if(y > 0) {
					if(x > 0) {
						if(region[(x - 1) + (y - 1) * w] == 2) {
							return false;
						}
					}
					if(x < w - 1) {
						if(region[(x + 1) + (y - 1) * w] == 2) {
							return false;
						}
					}
				}
				return true;
			}
			return false;
		} else {
			if(edgestate == 1 || edgestate == 2 || edgestate == 4 || edgestate == 8) {
				return true;
			}
			return false;
		}
	}

}