Jump to content

SQF Maze Generator

L3G0

By L3G0
in A2: Epoch Events (1.0.5.1)

 Share

Recommended Posts

L3G0 Newbie

L3G0

Posted
Posted

On 23th December one on my Admins told me about the Idea to create an Event, where we create a Maze with bots and a safe.
 
After i answered great Idea he wanted to start mapping, but i said no, why do it by hand if the can automatize it?
This is how it look like In game: 1 2 3 4 5
 
Yesterday i wrote the first working Version of this Event and now i want to share the core, the Maze Generator with you.
 
These are two example outputs of this Maze Generator:

[[1,0],[6,8],[9,0,9,1,1,1,1,1,1,11,8,1,9,0,9,1,1,1,0,10,9,8,0,9,8,9,9,1,1,2,8,1,1,8,0,8,8,1,1,10,8,9,1,8,1,8,0,9,1,2,8,8,8,1,0,9,1,0,9,2,8,8,1,9,1,0,9,1,8,3,8,9,0,8,9,1,0,1,1,10,8,8,1,8,8,1,9,1,8,2,12,5,4,4,13,4,5,4,5,7]]
[[0,6],[0,9],[9,1,1,9,1,9,1,1,9,3,9,0,8,0,8,1,8,8,0,10,8,9,1,1,1,0,8,9,1,2,8,8,9,1,9,1,1,0,9,10,8,8,0,8,8,9,0,9,0,2,8,1,1,8,1,0,9,0,9,3,1,9,0,9,1,1,8,9,0,10,8,0,9,8,1,8,8,1,1,10,9,1,0,9,0,8,1,1,8,2,12,12,5,4,5,12,5,5,5,6]]

The first Number in the Array is a Random Startpoint somewhere at the outer wall, the second is the end of the longest path where you could place the Vault and the third array describes how each chamber is configured using binary interpretation.
 
The Walls are Interpreted like the following schema:

    1
   ---
 8 | | 2
   ---
    4

This should be enough explanation if you want to write the ingame parser and wall spawner yourself. I don't public my event script at the moment because i don't want to let the noob admins, that are not able to code one line, take this work for their pay to win servers...
 
My Maze Generator is based on the Depth-first search algorithm and implemented as recursive backtracker like descripted here:

http://www.astrolog.org/labyrnth/algrithm.htm or http://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_backtracker
 
My first Idea was to write the prototype as callExtension but then i decided to instantly rewrite it in sqf, just for the fun :)
Here is my test code in C (don't complain about some strange design decisions, i wanted it to be easy convertible to sqf)

  Reveal hidden contents



Now the SQF Version of this Generator:

  Reveal hidden contents



The following benchmark Numbers got created with the following Code:

mazeGlobalVisitArray = [];
mazeGlobalChamberArray = [];
mazeGlobalDistance = 0;
mazeGlobalMaxDistance = 0;
mazeGlobalMaxEndPoint = [];

_mazeWidth = 20;
_mazeHeight = 20;

_t1 = diag_tickTime;
_maze = [_mazeWidth,_mazeHeight] call generateMaze;
diag_log format["creating Maze of size %1 x %2 took %3 seconds", _mazeWidth, _mazeHeight, (diag_tickTime - _t1)];

_mazeStart = _maze select 0;
_mazeEnd = _maze select 1;
_mazeWalls = _maze select 2;
diag_log format["%1", _maze];

The tests where run in the ArmA 2 Editor without any other concurrent scripts:

10 x 10 took 0.186523 seconds
20 x 20 took 1.2207 seconds
30 x 30 took 4.67871 seconds
40 x 40 took 15.7334 seconds
50 x 50 took 25.251 seconds
60 x 60 took 58.6504 seconds
60 x 100 took 217.323 seconds
60 x 200 took 654.614 seconds

As comparison, the 60x200 Maze took 0.01 seconds with the c implementation (including all printf). If you want to test it with 60 x 200 in the c code, comment out the "serialize_maze();".
 
Well Now the Task lets start a Tiny Competition:
My code can be improved a lot, its just a solution hacked down in one Day. Maybe you want write this or another Algorithm and compete to my Solution :)

Link to comment
Share on other sites
L3G0 Newbie

L3G0

Posted
  • Author
Posted
  On 12/25/2014 at 4:53 PM, Gr8Boi said:

What would i need to use to spawn it on a live server? seems pretty cool

This shows me, that you did not read my post. I explained how to spawn it, you just have to code it.

 

Be aware: I do not recommend to use the sqf based generator on live servers. I testet it on mine with 30 Users, to calculate the 20x20 Maze took over 200 seconds. If you realy want to use this on a live system, then write a dll in c/cpp and let it calculate the maze. This will take just some milliseconds instead of 200 seconds.

 

The Users needed 20 Minutes to solve it and escaped with the Price, so you should use at least a 25x25 Maze :D

Link to comment
Share on other sites
L3G0 Newbie

L3G0

Posted
  • Author
Posted
  On 12/26/2014 at 2:21 AM, BetterDeadThanZed said:

I'm guessing this is for A2 Epoch? I believe this probably belongs here: http://epochmod.com/forum/index.php?/forum/36-a2-epoch-events/

Nope it has nothing to do with Epoch, i just used the Epoch building structures to get some screenshots.

 

Its just the Algorithm to create a maze, how you spawn it, is another part.

I just wanted to creat an academic example what you can do, but you should not do! - Thats why i put it into off-topic.

Link to comment
Share on other sites
raymix Newbie

raymix

Posted
Posted

Oh, man, this is beautiful, thank you for sharing the SQF algorithm, L3G0.

 

One solution to this would be prefabs - a bunch of precalculated SQF files saved server side, then all you'd need to do is spawn them. Maybe give a random rotation to non essential walls if you want dynamics. It's obviously not what you are after, but it's certainly one way of doing it.

 

Good job, sir.

Link to comment
Share on other sites
L3G0 Newbie

L3G0

Posted
  • Author
Posted
  On 12/26/2014 at 5:48 AM, raymix said:
It's obviously not what you are after, but it's certainly one way of doing it.

Yes this a good way to do this, but an other solution would be to use c code and put it into an dll, then you are still fexible in size and variation :)

 

Since i like this type of nonsence Work, i plan to do two more versions, and 3D Version and maybe i will to write another version where you can choose some kind of complexity.

 

I will do some Benchmarking with ArmA 3, will see if it is faster then ArmA 2 :>

Link to comment
Share on other sites
  • 2 weeks later...
L3G0 Newbie

L3G0

Posted
  • Author
Posted

Since i am going to take an outtime from SQF and ArmA i want to share the last Version of my Maze Spawner which uses the Generator. If you use it and change anything of the code, share it in this thread! I want to see how you use it! :)
 
You will need the latest Version of WAI to use the Vehicle and Bot Spawn.

Maybe you will want to change these two lines in WAI/compile/custom_publish_vehicle.sqf:

_unit = _ailist select (floor(random(count _ailist)));
_unit addWeapon _carkey;

to:

if (count _ailist > 0) then {
	_unit = _ailist select (floor(random(count _ailist)));
	_unit addWeapon _carkey;
} else {
	diag_log "could not find a unit to add key to";
};

This will prevent the error Messages when spawning an vehicle without attached bots while wai_lock_vehicles == true.

 

If you want to use it on a productive system you should convert it to createVehicleLocal, it is not wise to use this script as it is on fully populated Epoch Servers.
 
Now the script, have fun :)

  Reveal hidden contents

Link to comment
Share on other sites
  • 2 months later...
seelenapparat Newbie

seelenapparat

Posted
Posted

hey L3G0, could you post your  custom_publish file?

I got it running so far, only the part with the carkey alludes me. :D

 

€: nevermind, figured that part out too.

 

the only thing now, that is not working the way I want it, is, how the bots spawn.

most of the time, they spawn at the entrance and not in the maze. can that be tweaked either?

 

€:€: figured that out as well. we had quiet our fun with it at our pvp/pve event today :)

Link to comment
Share on other sites
  • 2 years later...
Schalldampfer Newbie

Schalldampfer

Posted
Posted

Nice scripts... I hope I were here some years ago.
I'm working to make this work in 1.0.6.1 (maybe in 1.0.6.2)
 

generateMaze function

  Reveal hidden contents

and mission
 

  Reveal hidden contents


To run this event once, I put this code into server_functions.sqf

  Reveal hidden contents


 

Link to comment
Share on other sites
  • 1 month later...
L3G0 Newbie

L3G0

Posted
  • Author
Posted
  On 12/10/2017 at 2:04 PM, Schalldampfer said:

Nice scripts... I hope I were here some years ago.

Expand  

lool cool, i never would have though someone would find this here again. :D

Thank you for sharing your changes! :)

 

I thought i would have to add this to DesolationREDUX to revive it myself, but i am glad to see there is still use for it in ArmA 2. <3

Link to comment
Share on other sites
  • 3 months later...
Schalldampfer Newbie

Schalldampfer

Posted
Posted
  On 12/10/2017 at 2:04 PM, Schalldampfer said:

Nice scripts... I hope I were here some years ago.
I'm working to make this work in 1.0.6.1 (maybe in 1.0.6.2)
 

generateMaze function

  Reveal hidden contents

and mission
 

  Reveal hidden contents


To run this event once, I put this code into server_functions.sqf

  Reveal hidden contents


 

Expand  

the second sqf (mission) updated for new WAI:
 

  Reveal hidden contents

 

Link to comment
Share on other sites
Schalldampfer Newbie

Schalldampfer

Posted
Posted (edited)

new version to despawn maze after clearing
maze.sqf

  Reveal hidden contents


and this is the script to spawn maze after clearing

  Reveal hidden contents

(maze.sqf must have MazeDone=true;)

Edited by Schalldampfer
update for WAI2.2.6
Link to comment
Share on other sites

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
 Share
Go to topic listing
  • Advertisement

  • Discord

×
×
  • Create New...