[Release] Confused Minotaur - Procedural Labyrinth Script

[Rydygier 1317]

 

 

FILE

PLS 1.01 (Dropbox, APL-SA license)

 

 

INTRODUCTION

Lately had fun with some procedural maze/labyrinth algorithms, let others have fun too! 

 

PLS script takes as input a position, dimensions, wall segment class and used algorithm. Four algorithms implemented:

 

Randomized Kruskal's: fast, somewhat biased towards short dead ends ("kruskal").

Randomized Prim's: also fast and biased towards short dead ends ("prim").

Wilson's: slow, but unbiased/uniform results ("wilson"). 

Randomized Pseudo Prim's: Prim's with distinctive bias towards long open diagnonals due to additional condition not present in the original algorithm ("pseudoprim").

 

WIKI article

 

CODE

 

Initialization:

[(player modelToWorld [0,10,0]),120,120,"Land_PillboxWall_01_6m_round_F","kruskal"] call RYD_LAB_ConfusedMinotaur;
//[Bottom left corner position, x dimension (final dimension will be matched up to wall segment's bounding box real dimension), y dimension (ditto), wall segment class, used algorithm ("kruskal", "prim", "pseudoprim" or "wilson")]

 

Source:

Spoiler

RYD_LAB_ConfusedMinotaur = 
	{
	params ["_iPos","_xDim","_yDim","_wallClass","_algorithm"];
	
	RYD_LAB_Base = 
		{
		params ["_pos","_sizeX","_sizeY","_class"];
		
		_preWall = createVehicle [_class, [0,0,-1000], [], 0, "CAN_COLLIDE"];
		
		_bb = boundingBoxReal _preWall;
		deleteVehicle _preWall;
		
		_bbMin = _bb select 0;
		_bbMax = _bb select 1;

		_dimX = (_bbMax select 0) - (_bbMin select 0);
		_dimY = (_bbMax select 1) - (_bbMin select 1);
		_cellDim = _dimY;
		_dimIx = 0;

		if (_dimY < _dimX) then
			{
			_dimIx = 1;
			_cellDim = _dimX
			};
			
		_halfDim = _cellDim/2;
		
		_wallsX = ceil (_sizeX/_cellDim);
		_wallsY = ceil (_sizeY/_cellDim);
		
		_frameWalls = [];
		_wPos = +_pos;
		
		_model = toLower (getText (configFile >> "CfgVehicles" >> _class >> "model"));
		_mS = toArray _model;
		reverse _mS;
		_mS reSize ((count _mS) - 1);
		reverse _mS;
		_model = toString _mS;
		
		_axis = 0;
		
		for "_i" from 1 to 4 do
			{
			_wDir = 0;
			_walls = [];
			
			_cnt = _wallsX;
			if not ((_i mod 2) == 0) then
				{
				_cnt = _wallsY;
				if (_dimX > _dimY) then
					{
					_wDir = 90
					};			
				}
			else
				{
				if (_dimY > _dimX) then
					{
					_wDir = 90
					};			
				};
			
			_wPos = _wPos getPos [_halfDim,(_axis + 180)];
			_wPos = _wPos getPos [_halfDim,(_axis - 90)];
			
			for "_j" from 1 to _cnt do
				{
				_wPos = _wPos getPos [_cellDim,_axis];
				_wPos set [2,0];
				
				_seg = createSimpleObject [_model,(ATLtoASL _wPos)];
				_seg allowDamage false;
				_seg setDir _wDir;
				_seg setPosATL _wPos;
				_walls pushBack _seg
				};
				
			_axis = _axis + 90;
			_frameWalls pushback _walls;
			};
			
		_lX = count (_frameWalls select 1);
		_lY = count (_frameWalls select 0);
		
		_lineDir = 90;	
		if (_dimX > _dimY) then
			{
			_lineDir = 0
			};		
		
		_mAxis = 0;
		_gridWalls = [];
		_cells = [];
		
			{
			if (_foreachIndex > 1) exitWith {};
			_mainIx = _foreachIndex;
			
			_cnt = _lX;
			if (_foreachIndex == 1) then 
				{
				_cnt = _lY;
				_lineDir = 0;
				if (_dimX > _dimY) then
					{
					_lineDir = 90
					};
					
				_mAxis = 90;
				};
				
			_lastIx = (count _x) - 1;
			
				{
				if not (_foreachIndex == _lastIx) then
					{
					_lPos = position _x;
					_lPos = _lPos getPos [_halfDim,_mAxis];
					_lPos = _lPos getPos [_halfDim,(_mAxis + 90)];
					_lPos set [2,0];

					for "_i" from 1 to _cnt do
						{
						_seg = createSimpleObject [_model,(ATLtoASL _lPos)];
						_seg allowDamage false;
						_seg setDir _lineDir;
						_seg setPosATL _lPos;
						_gridWalls pushBack _seg;
						
						_cPos1 = _lPos getPos [_halfDim,_mAxis + 180];
						
						_myIx = _cells findIf 
							{
							((_cPos1 distance _x) < _halfDim)
							};
							
						if (_myIx < 0) then
							{
							_cells pushBack _cPos1;
							}
						else
							{
							_cPos1 = _cells select _myIx
							};
						
						_cPos2 = _lPos getPos [_halfDim,_mAxis];
									
						_myIx = _cells findIf 
							{
							((_cPos2 distance _x) < _halfDim)
							};
							
						if (_myIx < 0) then
							{
							_cells pushBack _cPos2;
							}
						else
							{
							_cPos2 = _cells select _myIx
							};
							
						_seg setVariable ["RYD_LAB_myCells",[_cPos1,_cPos2]];
											
						_lPos = _lPos getPos [_cellDim,(_mAxis + 90)];
						};
					};
				}
			foreach _x;
			}
		foreach _frameWalls;
		
		deleteVehicle ((_frameWalls select 1) select ((count (_frameWalls select 1)) - 1));
		deleteVehicle ((_frameWalls select 3) select ((count (_frameWalls select 3)) - 1));
		
		[_gridWalls,_cells]
		};
		
	RYD_LAB_KruskalR = 
		{
		params ["_gridWalls","_cells"];

		_sets = [];
		
			{
			_sets pushBack [_x]
			}
		foreach _cells;
		
		_cnt = count _gridWalls;
		
		for "_i" from 1 to _cnt do
			{
			_wall = selectRandom _gridWalls;
			_gridWalls = _gridWalls - [_wall];
			
			_myCells = _wall getVariable ["RYD_LAB_myCells",[[],[]]];
			
			_myCell = _myCells select 0;
			_mySet = _sets findIf 
				{
				(_myCell in _x)
				};
				
			_myCell2 = _myCells select 1;
			_mySet2 = _sets findIf 
				{
				(_myCell2 in _x)
				};

			if not (_mySet == _mySet2) then
				{
				(_sets select _mySet) appEnd (_sets select _mySet2);
				
				_sets set [_mySet2,0];
				_sets = _sets - [0];
				deleteVehicle _wall;
				}
			}
		};
		
	RYD_LAB_PrimR = 
		{
		params ["_gridWalls","_cells"];
		
		_maze = [];
		_wallList = [];
		
		_preWall = _gridWalls select 0;
		
		_bb = boundingBoxReal _preWall;
		
		_bbMin = _bb select 0;
		_bbMax = _bb select 1;

		_dimX = (_bbMax select 0) - (_bbMin select 0);
		_dimY = (_bbMax select 1) - (_bbMin select 1);
		_cellRad = (_dimX max _dimY) * 0.71;
		
		_cell = selectRandom _cells;	
		_maze pushBack _cell;
		
		_cWalls = [];
		
			{
			if ((_x distance2D _cell) < _cellRad) then
				{
				_cWalls pushBack _x
				};
			}
		foreach _gridWalls;

		_wallList appEnd _cWalls;
		
		while {((count _wallList) > 0)} do
			{
			_wall = selectRandom _wallList;
			_wallList = _wallList - [_wall];
			
			_myCells = _wall getVariable ["RYD_LAB_myCells",[[],[]]];
			_potCells = [];
			
				{
				if not (_x in _maze) then
					{
					_potCells pushBack _x;
					};
				}
			foreach _myCells;
			
			_newCell = [];
			if ((count _potCells) > 0) then
				{
				_newCell = selectRandom _potCells
				};
				
			if ((count _newCell) > 1) then
				{
				_gridWalls = _gridWalls - [_wall];
				_wallPos = position _wall;
				deleteVehicle _wall;			
				_maze pushBack _newCell;
				
					{
					if ((_x distance2D _newCell) < _cellRad) then
						{
						_wallList pushBackUnique _x
						};
					}
				foreach _gridWalls;			
				};
			}
		};
		
	RYD_LAB_PseudoPrimR = 
		{
		params ["_gridWalls","_cells"];
		
		_maze = [];
		_wallList = [];
		
		_preWall = _gridWalls select 0;
		
		_bb = boundingBoxReal _preWall;
		
		_bbMin = _bb select 0;
		_bbMax = _bb select 1;

		_dimX = (_bbMax select 0) - (_bbMin select 0);
		_dimY = (_bbMax select 1) - (_bbMin select 1);
		_cellRad = (_dimX max _dimY) * 0.71;
		
		_cell = selectRandom _cells;	
		_maze pushBack _cell;
		
		_cWalls = [];
		
			{
			if ((_x distance2D _cell) < _cellRad) then
				{
				_cWalls pushBack _x
				};
			}
		foreach _gridWalls;

		_wallList appEnd _cWalls;
		
		while {((count _wallList) > 0)} do
			{
			_wall = selectRandom _wallList;
			_wallList = _wallList - [_wall];
			
			_myCells = _wall getVariable ["RYD_LAB_myCells",[[],[]]];
			_potCells = [];
			
				{
				if not (_x in _maze) then
					{
					_potCells pushBack _x;
					};
				}
			foreach _myCells;
			
			_newCell = [];
			if ((count _potCells) > 0) then
				{
				_newCell = selectRandom _potCells
				};
				
			if ((count _newCell) > 1) then
				{
				_gridWalls = _gridWalls - [_wall];
				_wallPos = position _wall;
				deleteVehicle _wall;			
				_maze pushBack _newCell;
				
					{
					if ((_x distance2D _newCell) < _cellRad) then
						{
						if ((_x distance2D _wallPos) < (_cellRad * 1.1)) then
							{
							_wallList pushBackUnique _x
							}
						};
					}
				foreach _gridWalls;			
				};
			}
		};
		
	RYD_LAB_Wilson = 
		{
		params ["_gridWalls","_cells"];
		
		_preWall = _gridWalls select 0;
		_bb = boundingBoxReal _preWall;
		
		_bbMin = _bb select 0;
		_bbMax = _bb select 1;

		_dimX = (_bbMax select 0) - (_bbMin select 0);
		_dimY = (_bbMax select 1) - (_bbMin select 1);
		_cellDim = _dimX max _dimY;
		_cellRad = _cellDim * 0.71;
		
		_maze = [(selectRandom _cells)];
		_dirs = [0,90,180,270];
		
		while {((count _maze) < (count _cells))} do
			{
			_cPath = [];
			
			_cCell = selectRandom (_cells - _maze);
			_cDir = selectRandom _dirs;
			
			while {not (_cCell in _maze)} do
				{
				_nCellIx = _cells findIf {((_x distance2D (_cCell getPos [_cellDim,_cDir])) < _cellRad)};
				_badDirs = [];
				while {(_nCellIx < 0)} do
					{
					_badDirs pushBack _cDir;
					_cDir = selectRandom (_dirs - _badDirs);
					_nCellIx = _cells findIf {((_x distance2D (_cCell getPos [_cellDim,_cDir])) < _cellRad)};
					};
				
				_ix = _cPath findIf {(_cCell isEqualTo _x)};
				if (_ix < 0) then
					{
					_cPath pushBack _cCell;
					}
				else
					{	
					_cPath reSize (_ix + 1);
					};
					
				_cCell = _cells select _nCellIx;
				_cDir = selectRandom _dirs;
				_opDir = _cDir - 180;
				if (_opDir < 0) then
					{
					_opDir = _opDir + 360
					};
					
				_cDir = selectRandom (_dirs - [_opDir]);
				};

			_cnt = (count _cPath) - 1;
			
				{			
				_nextC = if not (_foreachIndex == _cnt) then
					{					
					(_cPath select (_foreachIndex + 1))
					}
				else
					{
					_cCell
					};
					
				_pair = [_x,_nextC];
				
					{
					_myCells = _x getVariable ["RYD_LAB_myCells",[[],[]]];
					if (({(_x in _myCells)} count _pair) == 2) exitWith
						{
						deleteVehicle _x
						}
					}
				foreach _gridWalls;
				_gridWalls = _gridWalls - [objNull];
				}
			foreach _cPath;
			
			_maze appEnd _cPath;
			};
		};
	
	_base = [_iPos,_xDim,_yDim,_wallClass] call RYD_LAB_Base;
	_code = switch (toLower _algorithm) do
		{
		case ("kruskal") : {RYD_LAB_KruskalR};
		case ("prim") : {RYD_LAB_PrimR};
		case ("pseudoprim") : {RYD_LAB_PseudoPrimR};
		case ("wilson") : {RYD_LAB_Wilson};
		default {{}};
		};

	_base call _code;
	};

 

 

[major-stiffy 281]

Like I said at your Youtube A-mazing !

[Rydygier 1317]

Just found, why Prim's wasn't look exactly like Prim's should - there was additional condition in the code - so I updated the script with proper Randomized Prim's, and since the result of previous "Prim's" was a proper maze too, it was kept as fourth algorithm under "pseudoprim".

[tortuosit 486]

Thanks Rydy!

[Twiznak 57]

WOW. Excellent work! I will use this as the interior for an ultimate CQB base. Thank you so much.