Programming question (completelt un-quake related.

El_Presidente

OK,

I'm sure there are one or two of you out there who know a bit about programming so here goes...

Whats the best method to program a robot to get out of a maze. I'm not lloking for anything too detailed but just GENERALLY, how is it done.

Does it hug a wall, keep taking random turns? etc.

any ideas??

Sonic

i did one of those when i was 12 bai , if u want ill mail u the algorithym and tell u how to do it BUT I'LL SEND NO CODE

Excelsior

Andy,
does the robot know if he is in the maze or not.
does he sense the wall
if the robot has these two features, you can use bool values.
if not, as rory says, you cling to the wall.

El_Presidente

Sonic, I don't want the code. I would like the algorithym though.

Send it to

andy_mullen@hotmail.com

---

Kev

The robot does not know if its in the maze. It does know however that when it reachs the end of the maze it will encounter a marker, so in a way it does know.

It can also detect walls.

Shinji

There's loads of stuff about this kind of general problem-solving out there on the web.

The algorithm you're looking for is a variation on a flood-fill. Test each possible pathway in order, marking off blocked routes. Nice elegant recursion is the best way to do it, but you can bodge it as well with a big dirty WHILE loop

Chaos

use a DFS or BFS algorithm. BFS would be better though

---

www.gibworld.com/chaos
ps? 0wns U

Shinji

Or alternatively, you could use a pile of meaningless TLAs, that should do the trick

Creeper

You mean DFT and BFT surely. Or do they teach things dirrerently in Portobello?

deRanged

wouldn't a bfs or dfs be the same as a bft or dft in this case ?
seeing as the robot (probably) can't search without actually moving.
or maybe they teach things differently in Cork.

Trojan

Be lazy.

Just keep touching the wall to the left and keep going til gets out.

Al.

ButcherOfNog

1. program it to move in a straight line
2. fit a chainsaw on the front of it

Chaos

bfs dfs was all they showed us

---

www.gibworld.com/chaos
ps? 0wns U

Gerry

while (!marker)
{
if no wall
{
move forward
}
else
{
turn left
}

if marker found
{
marker = true
}

byzantium!

Kali

course thats never going to come out of that
while loop gerry ..
quake equivalent: +left

DeV

That wont work if the starting position is this:


_| |__
| __ ..|
| |_|X|
|_____|

Where x is the robot's starting position.

or do they teach 2 dimensional physics differently in college these days.

The best solution depends on how far the robot can see. Everyone has presumed that it can only see one square, which may not be true and anyway, sight can be "created" with subroutines. Ie

Are_There_Any_Exits_Ahead()

returns true if there is and false if not.
But it may have the robot actually walk down and inspect the area and then walk back to its current location and then return.

Not efficient, but an interesting use of modular programming.

So, how far can this robot see?

Tom.


[This message has been edited by DeV (edited 17-11-99).]

Von

It's something like

step 1: keep going forward and check for right turns.
Step 2: Everytime u come to a wall then check for a right turn.
Step 3: If there's a right turn then repeat step 1.
Step 4: If there's no right turn then turn 180 degrees, check for a right turn and goto step 3.


represent the maze as a 2 dimensional array.



[This message has been edited by Von (edited 18-11-99).]

Gerry

how about this then

while (inmaze)
{
if nowall
{
go forward one space
turn left
}

else if wall
{
turn right
}
}

its not quite pseudo code and its
not quite c++
i call it d

Chaos

Naw that suxs ger

---

www.gibworld.com/chaos
ps? 0wns U

the celtic tiger

To tell you the truth "d" was invented several years ago and was a complete and utter flop. I however have invented a new language...I call it, "THE LANGUAGE OF LOVE".
I will now write a short program to print out to the screen, "the celtic tiger rules the world"... Here's how it goes:

If(tct is one sexy mother){
print to the screen<<"the celtic tiger rules the world"<<end of this line;
GGGGGGGGGGRRRRRROOOOOOWWWWWWWWLLLLLLLLLL!!!!!!
}

I mean, it's a little bit hard to understand, but if you look closely at the commands, you'll get the (int) main() idea!!!!!! For example..."print to the screen" tells the computer to print out whatever's after it to the screen. Similarly, "end of this line" means that it is the end of a line.....anything else will happen on a NEW line...simple really?
tct
peace man
and free loooove for all!!!!!!!

[This message has been edited by the celtic tiger (edited 18-11-99).]

the celtic tiger

what language are you all programming in? I know it's not the "LANGUAGE OF LOVE" cause it hasn't been commercialised yet. So, what is it?
and remember,,,,,
freeeeeeeeeeeee loooooooooooooooovvvvvvvvvvveeeee for all my friends...the human form is not an object to be coveted....share and share alike my friends....freeeee looove!!!!!!
peace man!!!!
tct

[This message has been edited by the celtic tiger (edited 18-11-99).]

quozl

Ok, serious reply.
Most of the above is useless, cept shinjis comment (for once
Do it with recursion.
at its starting point it will have a finite number of ways it can go. Have a function that calls itself for each of the available directions at a given location.
ie you start, try the first one, that then calls itself again on the new location, and then again on the next and so on. When you hit a dead end, end the recursion. This will bump you up one lvl and try the next option in the second last square. If all options in that square fail, it will bump up another lvl, eventually ending up at its original location, where it will try direction number two, then three until it runs out of options. P{resumably (unless your lecturer is a ****) one of these recursive searchs will stumble on the exit. At which point, either neatly return success through all the levels of the function, or just break out of it.
This will always find the exit, and unless its an absolutely huge maze should do it pretty quickly.
Oh and dump an ascii respresentation of the squares to the screen as you move through them, you'll draw the maze on screen then and is very handy for watching your robot and making sure he's not doing anything he shouldnt be
Quozl

Lucifer 2

Greg, ever think of doing some of our computer probelms, you know, the ones for college? havent seen you in ages (i know cause i havent got my zip disks back yet)
cya

Koopa

KALI posted this , he has l33tly haxored my password

[This message has been edited by Koopa (edited 18-11-99).]

Bullet

Just get a flagon and point the robot at it, trust me he'll soon find a way to that luvly flagon

Von

Recursion my hole. My way is how its done. Try a couple of sample mazes on paper to see what I mean. Simple, fast and no infinite loops.

quozl

You dont get infinite loops with recursion done properly

Trojan

I want some of whatever he's on!! [1]

Al.

1: Meaning TCT.

El_Presidente

Recursion was suggested to me but you forget one vital thing

Im an idiot and have no idea how to implement it.

Even if I did solve it using recursion they would be very suspcious as we havent covered it yet.

Ta anyway q

Von

Andy, it works for both. When you hit a wall and you can't go forward or right, turn 180 degrees and check if you can do a right turn. The idea is to always have a wall on your right.

El_Presidente

I'll try it again von but I still recon it gets caught in an infinite loop.

It gets to square (10, 1) fine and the goes straight up. It turns right at the wall at
(10, 11) and then travels to the wall at (14, 11) then turns right and goes to the bottom. The turns right and goes to (12, 1) and then turns right , goes to the wall at (12, 11) and turns right. Now its in an infinite loop.

BUT ENEOGH of this. Its friday and i'm going home now. I'll tackle this little bugger again next monday.


El

Von

You should turn right at 10,8 and again at 12,8 and go down to the bottom. Turn 180 degrees (face north) and you can then turn right and go along the bottom. You dig?

[This message has been edited by Von (edited 19-11-99).]

the celtic tiger

You said you'ld e-mail me andy....you lied.....you lied to me!
tct

El_Presidente

Von, check

http://www.compapp.dcu.ie/~cdaly/ca165/assignments/maze.html

your idea wont work for the bottom maze, it gets caught in an infinite loop.

Excelsior

Shouldnt this be on the programming board?
If you post it there I'll give you some valuable, insightful c++ algorithms.
If not you'll have to wait till I come to your house tomorrow.
But I'll bring a bag, expecting a 6pack of 7up for my trouble.
And you didnt pay me for that can you robbed from my locker last nite you critter.
AND check the humour board.
Kevin