Pages: [1]   Go Down
Author Topic: line maze algorithm  (Read 1920 times)
0 Members and 1 Guest are viewing this topic.
0
Offline Offline
Full Member
***
Karma: 0
Posts: 235
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hi
I am trying to find an algorithm so that my bot finds its way to the centre avoiding the obstacles in way..... smiley
sample track is http://tinypic.com/r/w7ivwi/4
the bot gets travel only once. so recording paths in trial runs wont work  :'(  it needs to travel from start to end in 1 go and fast not hitting any obstacles...
my current algorithm is right hand rule at the intersection but they seem a little too exhaustive way to go to centre...  smiley-sad is there some algorithm which can provide me with a faster time?
Thanx in advance  smiley
Logged

Norway@Oslo
Offline Offline
Edison Member
*
Karma: 12
Posts: 2033
loveArduino(true);
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

If you know the position of the obstacles: http://en.wikipedia.org/wiki/A*_search_algorithm
Logged

0
Offline Offline
Full Member
***
Karma: 0
Posts: 235
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

nope.... obstacles position dunno  smiley else i could have hard coded it smiley-grin any other suggestions?
Logged

Norway@Oslo
Offline Offline
Edison Member
*
Karma: 12
Posts: 2033
loveArduino(true);
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

You're in for a real treat if you're trying to find a solution to a maze without a left/right rule, or multiple trials.

Are you allowed to backtrack? Then you could 'remember' each decision made and try the other one(s) if the current did not lead to the target.
Logged

Canada
Offline Offline
Full Member
***
Karma: 0
Posts: 218
You will become one with the Arduino!
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

AlphaBeta was soooo close:

http://en.wikipedia.org/wiki/D*

Haven't tried this one yet though, can't say how it works.
Logged

0
Offline Offline
Full Member
***
Karma: 0
Posts: 235
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

yup i am allowed to back track  smiley I have made it like that... so if my bot finds a obstacle it puts a negative value on that path which tells my bot never to go there again. so when it reaches junction it will choose an of the other paths...  smiley but still i feel its a rubbish algorithm... smiley-sad takes too much time... is there an faster solution. becoz my destination is always center... and i face another problem too..  smiley-sad
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1254793692
« Last Edit: October 05, 2009, 08:49:15 pm by dev_000 » Logged

0
Offline Offline
Full Member
***
Karma: 0
Posts: 235
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

now these guys have changed the rules. now they tell the bot can go 4 multiple runs around the track for 7mins ie) it reaches the destination in middle and bot must trace back to starting position automatically (then timer resets) and then choose the shortest path. how do i do that?
i am using this as reference http://www.pololu.com/file/download/line-maze-algorithm.pdf?file_id=0J195
problem is that i only have around 2.5KB to code this storing the path and retracing and find the shortest path so can it be done in this space? rest of my code took around 4.7KB i only have a total 7.1KB  :-[
Logged

Norway@Oslo
Offline Offline
Edison Member
*
Karma: 12
Posts: 2033
loveArduino(true);
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

You should have plenty of space to implement a backtracking search in that space.

Each desicion need only two bits.
B00 = NOT_SET
B01 = left
B10 = right
B11 = straight ahed

This means you can store four desicions per byte, thus you have room for about 9600 decisions smiley
Logged

0
Offline Offline
Full Member
***
Karma: 0
Posts: 235
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I didnt understand... smiley-sad 2 bits? is it a datatype?  smiley B00 ?
Logged

Norway@Oslo
Offline Offline
Edison Member
*
Karma: 12
Posts: 2033
loveArduino(true);
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

http://en.wikipedia.org/wiki/Byte
http://en.wikipedia.org/wiki/Bit

B00 is the same as 0
B01 is the same as 1
B10 is the same as 2
B11 is the same as 3


Keep asking if it's still unclear smiley
Logged

0
Offline Offline
Full Member
***
Karma: 0
Posts: 235
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Ok. I understood that. How do I set individual bytes? (or preferrably bits :-/) Is there a data type for managing bytes, other than char?

And this sort of looks like assembly programming. Can I do assembly programming with arduino?

What is the size of an int variable. Is there any smaller data type like short int?
Logged

Norway@Oslo
Offline Offline
Edison Member
*
Karma: 12
Posts: 2033
loveArduino(true);
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

http://arduino.cc/en/Reference/Byte

http://arduino.cc/en/Reference/BitRead
http://arduino.cc/en/Reference/BitWrite
http://arduino.cc/en/Reference/BitSet
http://arduino.cc/en/Reference/BitClear
 smiley
Logged

Pages: [1]   Go Up
Jump to: