vinheim
Level: Smiter
Rank Points: 300
Registered: 05-31-2007
IP: Logged

File: Maze level.hold (1.4 KB)
Downloaded 74 times.
License: Public Domain

In the course I'm currently taking, every time I've had to learn a new programming language, one of the first assignments is to create the following effect using it. This was never too hard considering the algorithm never changes, so I decided to try it in the DRoD level editor.

What this is, is a character that follows the wall to its right in order to solve the problem "How do I get out of this maze?" Sometimes following the right wall leads to a much longer path to the exit than pathfinding, and sometimes (if the exit is in the middle of the maze) the character will never get out of the maze.

Here is the old script to understand the algorithm easier:


Here is the new script, completely infinite loop-free:


Attached is also a hold demonstrating it. If you stick around long enough using the old script, you'll see the script is not flawless as it is prone to infinite loop syndrome.

EDIT: Look below for the file Timos Maze level for the updated file. Shorter and easier to understand, though you need to make sure a new variable is made for each character. (These variables can be reused throughout the hold, however).

EDIT 2: New updated version uploaded.

EDIT 3: The 2nd line, Go to north1, can be changed to another "direction1" label depending on which wall you want the NPC to start following from the start.

---

[Last edited by vinheim at 10-31-2010 09:56 AM]

Timo006
Level: Smitemaster

Rank Points: 527
Registered: 07-19-2006
IP: Logged

Seems to be that there are the following problems:

1) The character that always turns in a loop-like way simply can't find a wall to its right.

2) If a character is unable to move during one turn, the script will get stuck in an infinite loop, since then it will only go through "label" and "go to" commands, leaving it unable to execute the remainder of the script.

____________________________
Drod Number: 3034; 8th person to see the Second Sky

vinheim
Level: Smiter
Rank Points: 300
Registered: 05-31-2007
IP: Logged

Number 1) isn't a problem. Most games that use wall-followers (like the one made by the same creator of the Hapland series) have that effect when there is no wall to the right. They circle around an enclosed corner.

As for 2), I've never experienced this before in scripting, so could you elaborate?

Timo006
Level: Smitemaster

Rank Points: 527
Registered: 07-19-2006
IP: Logged

File: Timos Maze level.hold (1.5 KB)
Downloaded 51 times.
License: Public Domain

"Go to" and "Label" commands don't take any turn to go through, and when you enclose the NPC, it can't move in any direction. This means that during that turn, it will go through all the "Else" parts of the script, and do so infinitely (Wich naturally causes an infinite loop). This however, causes the script to break, which means that the script will not continue.

Attached is a crude solution to the problem. Though it still needs some refining, it solves the problem of broken scripts.

____________________________
Drod Number: 3034; 8th person to see the Second Sky

---

[Last edited by Timo006 at 10-31-2010 12:49 AM]

vinheim
Level: Smiter
Rank Points: 300
Registered: 05-31-2007
IP: Logged

Brilliant! I had a feeling I'd have to use different variables for each character. I'm sure this isn't too much of a hassle since these variables can be reused for different rooms and I'm sure people won't keep like 20 of these around. For now, I'll recommend this post from my initial post. If I find a way around variables, I'll post it. As for now, I'm off so it won't be done til a few hours.

EDIT: The reason I never encountered this before in other programming languages is that it was easier to do a check on if there are 4 surrounding walls at the beginning of the program, and there was only 1 character moving around. Attached is the VB example, the other ones are in console and so are less attractive. <-- Nevermind this, problem solved.

---

[Last edited by vinheim at 10-31-2010 01:03 AM]

vinheim
Level: Smiter
Rank Points: 300
Registered: 05-31-2007
IP: Logged

Ooh, I already have an idea how to do this. Using labels east1, east2, east3, east4, and so on for the other directions, if at any point in the script the character is able to move, they go back to a "direction1" label. If they go through an else command, they go up 1 in the label (north1 to west2). At the "direction4" labels, if they can move, they go back to the "direction1" labels. If they cannot move, they Wait 0 and then go back to the "direction1" labels. I'll be sure to do this later.

vinheim
Level: Smiter
Rank Points: 300
Registered: 05-31-2007
IP: Logged

I had time to spare so... Newer version uploaded!

vinheim
Level: Smiter
Rank Points: 300
Registered: 05-31-2007
IP: Logged

File: Maze level.hold (3.1 KB)
Downloaded 56 times.
License: Public Domain

So quite the number of people have downloaded this, so I thought I should talk a bit more about this.

How the algorithm works

First of all, each label determines what direction the character is facing, whether it is moving or not.

Now as you can see from the script, if the character is moving north, it will check, as its top priority, if it can move east. If it can, it will move east and it will change its direction to east (so next turn, it will check if it can move south). This works for every direction. If you are going south, following the right wall means you'll be checking if you can move west.

Now how about the "else" part? You'll probably know, from looking at the way this character moves, that if it cannot move east, it will try to move north instead. Yet the script says it will change its direction to west. So how does he move forward? Well, the code after the "west" label will check, as its top priority if it can move north. So it moves north by turning left and moving right.

So the whole script is all about turning left and moving right. If you can move right, you will. Otherwise if you can move forward, you will turn left and move right. If you can only move left, you will turn left twice and move right. If you can only go backwards, you will turn left 3 times and move right.

The actual script, which contains 4 labels per direction stops the script from running into an infinite loop. Each label's number determines how many directions you have checked for emptiness before it. So east4 means you have checked the other 3 directions before it, so if it is blocked, all directions are blocked and the script will halt.

Puzzle Potential

Any scripted NPC can be used in a variety of different ways dependent on the architect's creativity. I've uploaded a hold demonstrating one way. These wraithwing wall-followers prevent tar growing onto pressure plates blocking your access to the last few monsters and the End Hold stairs. There is a roach queen spawning there whose roaches can disrupt the wall-followers movement and provoke a tar baby growing onto the pressure plate. You can see a demo at the title screen.

This is just one way of using them. As said in the End Hold message, you can use these guys as timers, from blocking hordes in a certain direction (if used right) or to trap them onto a pressure plate by having them follow a certain path that you manipulate by hitting orbs.

---

[Last edited by vinheim at 10-31-2010 10:45 PM]