Solve a Single Player Tron Game

Question

Solve a Tron Game

Tron is a great game, and if you haven't played it the internet has MANY online versions available. A fun challenge is to try to write an AI that plays Tron, which is normally much better than any human, thanks to their frame perfect dodging.

Even with their perfect dodging of walls, they still get themselves trapped easily.

Your task, is to write a script that when fed a map containing a single tron bike, that may already be partially filled, and output the actions required to fill it as much as possible.

The Task

From the letter p in the input, find the best moves to fill the most space in the maze, in as few iterations as possible, then output as a string of r(ight)u(p)l(eft)d(own), describing that path.

If you attempt to move into wall, your run is ended.

if you attempt to move where you have already been, your run is ended.

if your run contains an unexpected character, it is ended at that character.

Filling space refers to passing over it in your run. Your starting position is counted.

Input / Output

Your input will be through any valid method,

A maze, consisting of the characters # p (Pounds (0x23), Literal space (0x20) and the letter p lowercase (0x70)) one of the following forms

• A single multiline string
• An array of strings, split by lines
• An array of arrays, each containing a single character

You must output exactly

• A string or array of strings containing only the characters rlud case sensitive, describing your path through the maze.

You may use any reasonable permutation of these input and output format as well, such as bytes instead of characters.

Test Cases

Straight Forward.

Input:

#######
#p    #
#######

Example Output: rrrr

A Turn.

Input:

#######
#p    #
##### #
    # #
    ###

Example Output: rrrrdd

Box Filling.

Input:

#######
#p    #
#     #
#     #
#######

Example Output: rrrrdlllldrrrr

Complicated

Input:

#######
#p    #
#     #
#     #
##### #
    ###

Unfillable

Input:

 ########
 #p     #
 #     ##
###### #
#      #
##     #
 #######

Scoring

Your score is a combination of how fast your code runs and how many squares you fill of all the test cases.

Score is Total successful moves across Test Cases / Algorithmic Complexity Across Test Cases

So if your Algorithm has a complexity of O(a*b) Where 'a' is Maze Width and 'b' is Maze Height, then your Algorithm Complexity Total is (TestCase1Width * TestCase1Height) + (TestCase2Width * TestCase2Height)...

See More on Big O Notation

Highest score Wins!

Notes

• The input will always be an enclosed surrounding the p
• There will always be atleast 1 space to move from the start
• The area may not always be possible to fill completely.
• Your code should still work competitively on a random valid input. That is, do not cater just to the test cases.
• Standard Loopholes Apply
• this is a fastest-algorithm mutation, where both speed and space filled matters, not code length. Go ham.
• I'm particularly interested in a Java solution.
• Have fun!

Solution tester

var storedMap = "";
 function restoreMap(){
  document.getElementById("maze").value = storedMap;
 }
 function trymaze(){
  var score = "";
  var maze = document.getElementById("maze");
  storedMap = maze.value;
  var commands = document.getElementById("methodin");
  var converts = {r:{r:"─",u:"┌",d:"└",l:"─"},u:{r:"┘",u:"│",d:"│",l:"└"},d:{r:"┐",u:"│",d:"│",l:"┌"},l:{r:"─",u:"┐",d:"┘",l:"─"}}
  var dirs={l:{x:-1,y:0},u:{x:0,y:-1},r:{x:1,y:0},d:{x:0,y:1}};
  var last = "";
  var boxes = commands.value.replace(/./g, function(c){
   if(last==""){
    last = c;
    return {r:"╶",u:"╵",d:"╷",l:"╴"}[c];
   }
   var s = converts[c][last];
   last = c;
   return s;
  })
  var mMaze = maze.value.replace("p"," ").split("\n");
  var pp = maze.value.indexOf("p")
  var y = (maze.value.substring(1,pp).match(/\n/g)||[]).length;
  var x = ((maze.value.match(/.*p/)||[""])[0].length)-1;
  var path = commands.value.split("");
  for(s in path){
   tx = x + dirs[path[s]].x;
   ty = y + dirs[path[s]].y;
   mMaze[y] = mMaze[y].replaceAt(x, boxes[s]);
   if(!mMaze[ty]){
    alert("NO MAZE SEGMENT "+ty);
    break;
   }
   if(mMaze[ty].substring(tx,tx+1)!=" "){
    alert("HIT A WALL: "+tx+" "+ty+" \""+mMaze[ty].substring(tx,tx+1)+"\"")
    break;
   }
   score++;
   x=tx;
   y=ty;
   mMaze[y] = mMaze[y].replaceAt(x, "O");
  }
  if(document.getElementById("score").value){
   document.getElementById("score").value = document.getElementById("score").value + ", " + score;
  }else{
   document.getElementById("score").value = score;
  }
  maze.value = mMaze.join("\n");
 }

 String.prototype.replaceAt=function(index, character) {
     return this.substr(0, index) + character + this.substr(index+character.length);
 }

*{
  font-family: monospace;
 }
 textarea{
  width:30em;
  height:15em;
 }

<textarea id = "maze"></textarea>
 <form>
   <input type="text" id="methodin"></input>
   <input type="button" onclick="trymaze()" value="Try Maze"></input>
   <input type="button" onclick="restoreMap()" value="Reset Maze"></input><br/>
   <input type="text" id="score"></input>
 </form>