Project

General

Profile

« Previous | Next » 

Revision 1892

First commit of the Collision Avoid Code. It probably doesn't work as-is.
This code is supposed to detect when multiple robots can cross an intersection at the same time.

Authors:
-Alexander Lam
-Willis Chang

How this works
First, a structure:
Dir0
[0 ][4 ]
Dir1 [7][8 ][9 ][1] Dir3
[3][11][10][5]
[6 ][2 ]
Dir2

[0] represents the right lane of the north direction
[5] represents the left lane of the east direction.
[2] represents the right lane of the south direction.
...and so on.
[9] represents the north-east sector of the intersection
[10] represents the south-east sector of the intersection
...and so on.

These can be represented using a 16-bit int.

The bot at the head of the queue creates a 16-bit int and fills in the path it will traverse. For example, it begin at east and go to west:

[ ][ ]
[x][x][x][x]
[ ][ ][ ][ ]
[ ][ ]

Implementation notes: to fill in a path, simply OR in. The bot's personal path can be kept in memory as long as it is in the queue for that intersection.

and then it sends this int in some packet, let's call it WCOLLISIONAVOID, and it begins to cross the intersection.

the next bot in the queue fills in its path - if it finds a bit set along any of its path, then it won't fill the path in. it will only fill in the bit indicating where it is and then send it in WCOLLISIONAVOID. FOr example, it begins at south and travels to north. Obvious ceavat: making the linked work with this (taking a link out).

[ ][ ]
[x][x][x][x]
[ ][ ][ ][ ]
[ ][x]

otherwise, it fills in its path, and sends it in a WCOLLISIONAVOID packet, and then traverses the intersection. for example, it travels from west to south:
[ ][ ]
[x][x][x][x]
[x][x][ ][ ]
[x][x]

Implementation notes: use AND on the recieved map and the bot's personal path and check if it's NON-ZERO. if so, that path has a filled in bit along it and it cannot go.
this will continue until 1, 0, 7, and 6 are filled in or the bot is the last on the queue. When this happens, the bot that recieves this packet will just sit and chill.

once a WINTERSECTIONEXIT packet is received, the first bot does this process again, and any bot in the process of thinking about the map aborts thinking about the map.

Files

  • added
  • modified
  • copied
  • renamed
  • deleted

View differences