Go Down

Topic: line maze algorithm (Read 2862 times)previous topic - next topic

000

Oct 05, 2009, 05:52 pm
Hi
I am trying to find an algorithm so that my bot finds its way to the centre avoiding the obstacles in way.....
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...   is there some algorithm which can provide me with a faster time?

AlphaBeta

#1
Oct 05, 2009, 06:31 pm
If you know the position of the obstacles: http://en.wikipedia.org/wiki/A*_search_algorithm

000

#2
Oct 05, 2009, 07:27 pm
nope.... obstacles position dunno   else i could have hard coded it any other suggestions?

AlphaBeta

#3
Oct 05, 2009, 09:11 pm
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.

Spinlock

#4
Oct 05, 2009, 09:15 pm
AlphaBeta was soooo close:

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

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

000

#5
Oct 06, 2009, 03:25 amLast Edit: Oct 06, 2009, 03:49 am by dev_000 Reason: 1
yup i am allowed to back track   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...   but still i feel its a rubbish algorithm... takes too much time... is there an faster solution. becoz my destination is always center... and i face another problem too..
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1254793692

000

#6
Oct 07, 2009, 05:41 am
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?
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

AlphaBeta

#7
Oct 07, 2009, 05:52 am
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

000

#8
Oct 07, 2009, 07:08 am
I didnt understand... 2 bits? is it a datatype?   B00 ?

AlphaBeta

#9
Oct 07, 2009, 08:42 am
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

000

#10
Oct 07, 2009, 11:18 am
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?

AlphaBeta

#11
Oct 07, 2009, 02:01 pm

Go Up

Please enter a valid email to subscribe