search

darozak / Advolition

1 stars 0 forks source link

Design a robot that explores the dungeon #72

Closed darozak closed 4 months ago

darozak commented 4 months ago

It should be possible to create a demo robot that moves through the dungeon by moving from one door to the next and recording which doors it has already been through. Can I create a class that handles this?

darozak commented 4 months ago

I created a routine that allow the robot to identify a door and move towards it (https://github.com/darozak/Advolition/commit/3b262e3e1b4c44f66a140823181c5c6a104edd09). However, it also needs to move towards areas outside of it's scan range if a door isn't available.

darozak commented 4 months ago

The robot now moves towards unexplored spaces as well as un-transited doorways (https://github.com/darozak/Advolition/commit/ce86bbfe9a6b28dce7c43571b2e545370dbca21e). However, this is an imperfect routine in which the robot often gets stuck bouncing between nearby locations or turns around before reaching an unexplored bend in the hallway.

darozak commented 4 months ago

I was able to improve the routine by not evaluating the robot's current position (https://github.com/darozak/Advolition/commit/abff836b290fa5451a10201227261a76c97ddae2). This avoids the routine indicating that all routes are blocked because the robot is standing on a door, which is considered to be non transparent.

There is still an issue with the robot being blind to distant turns in the hallway. I need figure out a way for the robot to move fully into the room or hallway before evaluating it's options. What if the robot always moves to a target at the end of it's scan range (i.e. it won't move into void spaces) before re-evaluating? This could solve some of the problems but not all of them.

darozak commented 4 months ago

It might also work to have the robot be near-sighted and only avoid obstructions that are close to the robot.

darozak commented 4 months ago

The near-sighted strategy doesn't work. The robot ends up getting lost in the middle of a room. This may be because it doesn't attempt to maintain it's direction when left with given the option of going to an open space in front of it or behind it. It will always pick the left-most open space unless there's an obstacle in that direction. I need to have the robot prioritize options in the direction that it was heading.

Another solution might be to only consider tiles that are visible in the most recent scan and then head towards doors or open tiles that are on the edge of the scan.

darozak commented 4 months ago

I thnik a simple solution may be to identify all open spaces to which the robot has an unobstructed path and go to the one that it has not visited in the longest amount of time.

darozak commented 4 months ago

I think I'm on the right path. I've modified the routine so that the robot prioritizes exploration of unscanned regions over doors and doesn't look for obstructions near the end of a long path. This last change allows it to approach blind turns before giving up on them. (https://github.com/darozak/Advolition/commit/48169fc16b4a21581c0e884e241b7b7dc3b54755) I still need to add a script which allows the robot to backtrack over explored spaces (i.e. not near unscanned tiles) if it is already in familiar territory.

darozak commented 4 months ago

I further improved the explorer class by ensuring the robot doesn't consider it's current location as a possible destination. I also give it the option of retracing its steps if no "new" spaces are readily available. (https://github.com/darozak/Advolition/commit/b71586c9a685187089f5fbbf78372975ac9c6329). There are still occasions when the robot gets caught in a loop. But for now this is a fairly successful routine.