Building maze to maximize shortest path, may be given waypoints and teleports How would you go about solving this problem?  Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores?  (Assuming sizes between 8x8 and 30x30.  Using C or C++ if that matters)  Or, is this so complex that it would take way longer?

There is an area, where an automated traveler follows a shortest path algorithm at all times.  Playing the builder, find the way to maximize the number of points the traveler must visit.

The area is typically between 8x8 and 30x30, given in the form:

.F......
......a.
........
........
.....1X.
........
.A......
........
..O.....
.X......
..X.....
..X.....


Where there is:


Always a single O, the starting point
Always a single F, the ending point
Always many ., empty points that can either be traveled or built on
Sometimes X, points designating they are blocked for traveling or building
Sometimes pairs of letters (i.e. A and a, but never F, O, or X), indicating a teleport when visiting the uppercase letter for the first time to the lowercase letter
Sometimes numbers (i.e. 1), designating waypoints


The automated traveler follows a shortest path algorithm at all times.  It must begin at the starting point, if there are waypoints pass over them in order, and finish at the ending point.  The traveler may pass over the ending point or subsequent waypoints early, but the game doesn't end and the waypoints aren't counted as visited, until they are the active next destination.  If there are any, the traveler must not pay attention to any teleport spots; they must take the shortest path between points as if they cannot see these teleport spots.  The exception to this rule is if there are multiple paths with the shortest length between last source to next destination and one of them travels through an active teleport spot, the path with the teleport must be taken.  (Otherwise, can choose any of the multiple shortest paths.)  If the shortest path forces them into a teleport spot, they teleport the first time they visit the uppercase letter to the corresponding lowercase letter.  The traveler can move horizontally and vertically.  The traveler can move diagonally between two points if the 2x2 square containing both points is clear of blocking points.

So, if the traveler needs to travel from the lower left to upper right point, here they can move diagonally and only count 2 moves:

..
..


But here, again traveling from the lower left to upper right point, they cannot move diagonally and must count 3 moves:

X.
..


The game always starts with an open path to reach all required destinations.

You, the builder, get to take all of your actions first, and none once you decide you are complete and allow the traveler to begin.  The builder can place additional X points that block travel on them, but they cannot make it impossible to reach any of the required destinations.  The builder cannot place any other points, such as more teleports or waypoints.  The builder cannot remove anything given to them already in the area (other than replace empty points.)  Strategy may include blocking points to force: otherwise out of the way travel; backtracking; and traveling between teleports.  Optimal strategy might include trying to connect the starting, ending, and destination teleport spots in short paths, and forcing a long backtracking path to waypoints.

This is to come up with possible strategies for a tower defense game.  Certain aspects of the game, such as multiple waves, limitations on resources, and attack towers, are ignored to simplify and just focus on the maze-like aspect of the game.
Just a note: even the simpler version without waypoints and teleports is NP-hard:
Start with a maze in which the dots mimic the edges of a grid graph $G$ of max degree 3,  and $X$s are placed &quot;around&quot; them (the dots are &quot;corridors&quot;). Put the $O$ in a corner and the $F$ near it with a dot in the middle.
Maximizing the shortest path (adding more Xs) is equivalent to finding an Hamiltonian path in the original graph $G$ which is NP-complete (each new $X$ must block a &quot;corridor&quot;, i.e. it removes an edge of $G$).