AI Homework #4

wumpus.dart

/*
  Ali Ghanbari - 970216657
  AI Homework 4 - Wumpus World
 */

import 'package:flutter/material.dart';

///#######################################
/// constants
/// ######################################

const n = 4;
enum Action { LeftTurn, RightTurn, Forward, Grab, Release, Shoot, None }
enum Orientation { Right, Left, Up, Down }
enum Sense { Stench, Breeze, Glitter }

///#######################################
/// Classes
/// ######################################
class Position {
  final int x, y;

  Position(this.x, this.y);

  Iterable<Position> get neighbours => [
        Position(x + 1, y),
        Position(x - 1, y),
        Position(x, y + 1),
        Position(x, y - 1),
      ].where(Position.valid);

  static bool valid(Position p) => p.x > 0 && p.x <= n && p.y > 0 && p.y <= n;

  int distance(Position to) => (x - to.x).abs() + (y - to.y).abs();

  @override
  bool operator ==(Object other) {
    if (other is Position) {
      return x == other.x && y == other.y;
    }
    return false;
  }

  @override
  int get hashCode => x.hashCode ^ y.hashCode * 31;

  Orientation orientationFor(Position next) {
    final neig = {
      Position(x + 1, y): Orientation.Right,
      Position(x - 1, y): Orientation.Left,
      Position(x, y + 1): Orientation.Up,
      Position(x, y - 1): Orientation.Down,
    };
    Orientation? o = neig[Position(next.x, next.y)];
    if (o == null) {
      throw 'invalid route!';
    }
    return o;
  }

  @override
  String toString() => '($x, $y)';
}

class Physics extends Position {
  bool stench = false, breeze = false, glitter = false;
  bool visited = false;
  bool pit = false, wumpus = false;

  Physics(int x, int y) : super(x, y);

  List<Sense> get senses => [
        if (breeze) Sense.Breeze,
        if (stench) Sense.Stench,
        if (glitter) Sense.Glitter,
      ];

  @override
  String toString() =>
      '${put(pit, 'P')}${put(wumpus, 'W')}${put(stench, 's')}${put(breeze, 'b')}${put(glitter, 'g')}${put(visited, '-Safe')}';
}

class KB {
  final List<List<Physics>> _physics;

  KB(int width, int height)
      : _physics = gen2dArray(height, width, (i, j) => Physics(i + 1, j + 1));

  final _fringe = <Position>[
    Position(2, 1),
    Position(1, 2),
  ];

  Iterable<Physics> get fringe => _fringe.map(fromPosition);

  bool wumpus(Physics tile) {
    return _check(tile, Sense.Stench, Sense.Breeze);
  }

  bool pit(Physics tile) {
    return _check(tile, Sense.Breeze, Sense.Stench);
  }

  bool _check(Physics tile, Sense sense, Sense inverSense) {
    if (tile.visited) return false;
    var neighbors =
        tile.neighbours.map(fromPosition).where((t) => t.visited).toList();
    if (neighbors.isEmpty) return false;
    if (neighbors.length == 1) {
      var neighbor = neighbors.single.senses;
      if (!neighbor.contains(sense)) return false;
      if (neighbor.contains(inverSense)) return false;
    }
    return neighbors
        .map((t) => t.senses.contains(sense))
        .reduce((t1, t2) => t1 && t2);
  }

  void addToFringe(Position pos) {
    if (!fromPosition(pos).visited) {
      _fringe.add(pos);
    }
  }

  void removeFromFringe(Physics tile) {
    _fringe.removeWhere((p) => p.x == tile.x && p.y == tile.y);
  }

  Physics fromPosition(Position p) => _physics[p.x - 1][p.y - 1];
}

class Player {
  // properties
  final KB kb;
  int x = 1;
  int y = 1;
  Orientation orientation = Orientation.Right;
  Action action = Action.None;
  final plan = <Action>[];
  int performance = 0;
  bool holdingGold = false;
  var arrows = 1;
  final Function(int) onWin;

  Position get position => Position(x, y);

  Physics get currentTile => kb.fromPosition(position);

  // constructor & initializer
  Player(int width, int height, this.onWin) : kb = KB(width, height);

  // PL-Wumpus-Agent
  Action step(List<Sense> Function(Position p) percept) {
    // update position based on action
    processAction(action);
    currentTile.visited = true;
    kb.removeFromFringe(currentTile);

    // add sense to kb
    final senses = percept(position);
    currentTile.stench = senses.contains(Sense.Stench);
    currentTile.breeze = senses.contains(Sense.Breeze);
    currentTile.glitter = senses.contains(Sense.Glitter);
    if (senses.contains(Sense.Glitter)) {
      if (holdingGold) {
        onWin(performance);
        return Action.None;
      }
      action = Action.Grab;
      performance += 1000;
      onWin(performance);
    } else if (plan.isNotEmpty) {
      action = plan.removeAt(0);
    } else if (kb.fringe.any((p) => !kb.wumpus(p) && !kb.pit(p))) {
      final targets = kb.fringe.where((p) => !kb.wumpus(p) && !kb.pit(p)).toList()..shuffle();
      plan.addAll(planRoute(currentTile, orientation, targets.first));
      action = plan.removeAt(0);
    } else {
      action = getRandomAction();
    }
    return action;
  }

  void processAction(Action action) {
    switch (action) {
      case Action.LeftTurn:
        switch (orientation) {
          case Orientation.Right:
            orientation = Orientation.Up;
            break;
          case Orientation.Left:
            orientation = Orientation.Down;
            break;
          case Orientation.Up:
            orientation = Orientation.Left;
            break;
          case Orientation.Down:
            orientation = Orientation.Right;
            break;
        }
        break;
      case Action.RightTurn:
        switch (orientation) {
          case Orientation.Right:
            orientation = Orientation.Down;
            break;
          case Orientation.Left:
            orientation = Orientation.Up;
            break;
          case Orientation.Up:
            orientation = Orientation.Right;
            break;
          case Orientation.Down:
            orientation = Orientation.Left;
            break;
        }
        break;
      case Action.Forward:
        switch (orientation) {
          case Orientation.Right:
            if (x < n) x++;
            break;
          case Orientation.Left:
            if (x > 1) x--;
            break;
          case Orientation.Up:
            if (y < n) y++;
            break;
          case Orientation.Down:
            if (y > 1) y--;
            break;
        }
        performance--;
        position.neighbours.forEach(kb.addToFringe);
        break;
      case Action.Grab:
        holdingGold = true;
        break;
      case Action.Release:
        holdingGold = false;
        break;
      case Action.Shoot:
        if (arrows > 0) {
          // TODO: shoot
          performance -= 10;
        }
        break;
      case Action.None:
      default:
        break;
    }
  }

  // Graph Route Search
  Iterable<Action> planRoute(
    Physics node,
    Orientation orientation,
    Position goal,
  ) sync* {
    // properties
    final heuristics = (Physics t1, Physics t2) =>
        t1.distance(goal).compareTo(t2.distance(goal));

    // logic
    if (node == goal) return;

    var successors = node.neighbours
        .map(kb.fromPosition)
        .where((t) => !kb.wumpus(t) && !kb.pit(t))
        .toList()
          ..sort(heuristics);

    var next = successors.first;
    var nextOrientation = node.orientationFor(next);

    yield* changeOrientation(orientation, nextOrientation);
    yield Action.Forward;
  }

  Action getRandomAction() {
    final ra = [Action.Forward, Action.LeftTurn, Action.RightTurn]..shuffle();
    return ra.first;
  }
}

///#######################################
/// Utility Functions
/// ######################################

List<List<T>> gen2dArray<T>(
  int height,
  int width,
  T Function(int i, int j) factory,
) {
  return List.generate(
    width,
    (x) => List.generate(
      height,
      (y) => factory(x, y),
    ),
  );
}

Iterable<Action> changeOrientation(Orientation current, Orientation to) sync* {
  if (current == to) return;
  switch (current) {
    case Orientation.Right:
      if (to == Orientation.Up)
        yield Action.LeftTurn;
      else if (to == Orientation.Down)
        yield Action.RightTurn;
      else {
        yield Action.RightTurn;
        yield Action.RightTurn;
      }
      break;
    case Orientation.Left:
      if (to == Orientation.Up)
        yield Action.RightTurn;
      else if (to == Orientation.Down)
        yield Action.LeftTurn;
      else {
        yield Action.RightTurn;
        yield Action.RightTurn;
      }
      break;
    case Orientation.Up:
      if (to == Orientation.Left)
        yield Action.LeftTurn;
      else if (to == Orientation.Right)
        yield Action.RightTurn;
      else {
        yield Action.RightTurn;
        yield Action.RightTurn;
      }
      break;
    case Orientation.Down:
      if (to == Orientation.Left)
        yield Action.RightTurn;
      else if (to == Orientation.Right)
        yield Action.LeftTurn;
      else {
        yield Action.RightTurn;
        yield Action.RightTurn;
      }
      break;
  }
}

List<T> flatten<T>(List<List<T>> mat) {
  return [
    for (var i = 0; i < mat.length; i++)
      for (var j = 0; j < mat.length; j++) mat[j][i]
  ];
}

String put(bool? b, String c) => b ?? false ? c : '';

///#######################################
/// Game Manager
/// ######################################

mixin GameManager on State<WumpusGame> {
  var started = false;
  late List<Action> history;
  late Player player;
  late List<List<Physics>> world;

  static List<List<Physics>> emptyWorld() => [
        for (int x = 1; x <= n; x++)
          [for (int y = 1; y <= n; y++) Physics(x, y)]
      ];

  void togglePit(Position p) {
    final tile = getTile(p);
    if (tile.wumpus) return;
    tile.pit = !tile.pit;
    tile.neighbours
        .where(Position.valid)
        .map(getTile)
        .forEach((t) => t.breeze = tile.pit);
  }

  void toggleWumpus(Position p) {
    final tile = getTile(p);
    if (tile.pit) return;
    tile.wumpus = !tile.wumpus;
    for (var t in tile.neighbours.map(getTile)) {
      t.stench = tile.wumpus;
    }
  }

  void toggleGold(Position p) {
    final tile = getTile(p);
    tile.glitter = !tile.glitter;
  }

  Physics getTile(Position p) => world[p.x - 1][p.y - 1];

  List<Sense> getPerception(Position p) {
    final tile = getTile(p);
    if (tile.wumpus || tile.pit) gameOver();
    return tile.senses;
  }

  void step() {
    setState(() {
      var action = player.step(getPerception);
      history.add(action);
    });
  }

  void gameOver() {
    showDialog(
      context: context,
      builder: (context) {
        return AlertDialog(
          title: Text('Game Over!'),
          actions: [TextButton(child: Text('Reset'), onPressed: _pop(reset))],
        );
      },
    );
  }

  void win(int performance) {
    showDialog(
      context: context,
      builder: (context) {
        return AlertDialog(
          title: Text('Agent Won!'),
          content: Text('Performance: $performance'),
          actions: [TextButton(child: Text('Reset'), onPressed: _pop(reset))],
        );
      },
    );
  }

  void reset() {
    setState(() {
      exampleWorld1();
      started = false;
    });
  }

  void start() {
    setState(() {
      started = true;
    });
  }

  // pop ui dialog
  void Function() _pop(Function f) => () {
        Navigator.pop(context);
        f();
      };

  void Function() _state(Function f) => () {
    setState(() {
      f();
    });
  };

  void exampleWorld1() {
    world = emptyWorld();
    player = Player(n, n, win);
    history = <Action>[];
    toggleWumpus(Position(1, 3));
    togglePit(Position(3, 1));
    togglePit(Position(3, 3));
    togglePit(Position(4, 4));
    toggleGold(Position(2, 3));
  }

  void exampleWorld2() {
    world = emptyWorld();
    player = Player(n, n, win);
    history = <Action>[];
    toggleWumpus(Position(2, 3));
    togglePit(Position(1, 4));
    togglePit(Position(4, 4));
    togglePit(Position(4, 2));
    toggleGold(Position(3, 3));
  }

  void exampleWorld3() {
    world = emptyWorld();
    player = Player(n, n, win);
    history = <Action>[];
    toggleWumpus(Position(1, 3));
    togglePit(Position(2, 2));
    togglePit(Position(3, 2));
    togglePit(Position(4, 2));
    toggleGold(Position(1, 2));
  }

  void exampleWorld4() {
    world = emptyWorld();
    player = Player(n, n, win);
    history = <Action>[];
    toggleWumpus(Position(3, 2));
    togglePit(Position(1, 4));
    togglePit(Position(3, 1));
    togglePit(Position(4, 2));
    togglePit(Position(4, 4));
    toggleGold(Position(1, 3));
  }
}

///#######################################
/// UI
/// ######################################
void main() => runApp(MaterialApp(home: WumpusGame()));

class WumpusGame extends StatefulWidget {
  const WumpusGame({Key? key}) : super(key: key);

  @override
  _WumpusGameState createState() => _WumpusGameState();
}

class _WumpusGameState extends State<WumpusGame> with GameManager {
  @override
  void initState() {
    super.initState();
    exampleWorld1();
  }

  @override
  Widget build(BuildContext context) {
    return Scaffold(
      appBar: AppBar(
        title: Text('Wumpus World by Ali Ghanbari'),
        centerTitle: true,
      ),
      body: Directionality(
        textDirection: TextDirection.rtl,
        child: ListView(
          children: [
            Padding(
              padding: const EdgeInsets.all(8.0),
              child: Text(
                started ? 'Agent Knowledge Base' : 'World Overview',
                style: TextStyle(fontSize: 21),
                textAlign: TextAlign.center,
              ),
            ),
            WorldGrid(
              key: UniqueKey(),
              world: started ? player.kb._physics : world,
              player: player,
            ),
            if(!started) ButtonBar(
              alignment: MainAxisAlignment.center,
              children: [
                ElevatedButton(
                  onPressed: _state(exampleWorld1),
                  child: Padding(
                    padding: const EdgeInsets.all(8.0),
                    child: Text('World 1'),
                  ),
                ),
                ElevatedButton(
                  onPressed: _state(exampleWorld2),
                  child: Padding(
                    padding: const EdgeInsets.all(8.0),
                    child: Text('World 2'),
                  ),
                ),
                ElevatedButton(
                  onPressed: _state(exampleWorld3),
                  child: Padding(
                    padding: const EdgeInsets.all(8.0),
                    child: Text('World 3'),
                  ),
                ),
                ElevatedButton(
                  onPressed: _state(exampleWorld4),
                  child: Padding(
                    padding: const EdgeInsets.all(8.0),
                    child: Text('World 4'),
                  ),
                ),
              ]),
            ButtonBar(
              alignment: MainAxisAlignment.center,
              children: [
                if (!started)
                  ElevatedButton(
                    onPressed: start,
                    child: Padding(
                      padding: const EdgeInsets.all(8.0),
                      child: Text('Start'),
                    ),
                  ),
                if (started)
                  ElevatedButton(
                    onPressed: step,
                    child: Padding(
                      padding: const EdgeInsets.all(8.0),
                      child: Text('Step'),
                    ),
                  ),
                if (started)
                  ElevatedButton(
                    onPressed: reset,
                    child: Padding(
                      padding: const EdgeInsets.all(8.0),
                      child: Text('Reset'),
                    ),
                  ),
              ],
            ),
            SizedBox(
              height: 180,
              child: SingleChildScrollView(
                child: Column(
                  children: history.reversed.map((a) => Text('$a')).toList(),
                ),
              ),
            ),
          ],
        ),
      ),
    );
  }
}

class WorldTile extends StatelessWidget {
  final Physics physics;
  final Player player;

  const WorldTile({Key? key, required this.physics, required this.player})
      : super(key: key);

  @override
  Widget build(BuildContext context) {
    var death = physics.pit || physics.wumpus;
    return Stack(
      children: [
        Container(
          alignment: Alignment.center,
          decoration: BoxDecoration(border: Border.all()),
          child: Column(
            mainAxisAlignment: MainAxisAlignment.spaceEvenly,
            children: [
              if (physics.wumpus) WumpusImage(),
              if (physics.pit) PitImage(),
              if (physics.stench && !death) StenchImage(),
              if (physics.breeze && !death) BreezeImage(),
              if (physics == player.position) AgentImage(player.orientation),
            ],
          ),
        ),
        if (physics.visited)
          Align(
            alignment: Alignment.topLeft,
            child: Tag('S', Colors.cyan),
          ),
        if (player.kb.pit(physics))
          Align(
            alignment: Alignment.bottomCenter,
            child: PitImage(true),
          ),
        if (player.kb.wumpus(physics))
          Align(
            alignment: Alignment.bottomCenter,
            child: WumpusImage(true),
          ),
        if (player.kb._fringe.contains(physics))
          Align(
            alignment: Alignment.topRight,
            child: Tag('F', Colors.purpleAccent),
          ),
        if (physics.glitter)
          Align(
            alignment: Alignment.bottomLeft,
            child: Tag('G', Colors.yellow[700]!),
          ),
      ],
    );
  }
}

class WorldGrid extends StatelessWidget {
  final List<List<Physics>> world;
  final Player player;

  const WorldGrid({Key? key, required this.world, required this.player})
      : super(key: key);

  @override
  Widget build(BuildContext context) {
    final ruler = List.generate(
        n,
        (i) => Padding(
              padding: const EdgeInsets.all(8.0),
              child: Text('${(n - 1 - i) + 1}'),
            ));
    final grid = GridView.count(
      shrinkWrap: true,
      crossAxisCount: n,
      children: flatten(world)
          .reversed
          .map((tile) => WorldTile(physics: tile, player: player))
          .toList(),
    );
    return ConstrainedBox(
      constraints: BoxConstraints(
        maxHeight: MediaQuery.of(context).size.width + 16,
      ),
      child: Column(
        children: [
          Expanded(
            child: Row(
              children: [
                Expanded(child: grid),
                Column(
                  children: ruler,
                  mainAxisAlignment: MainAxisAlignment.spaceAround,
                ),
              ],
            ),
          ),
          Row(
            children: ruler,
            mainAxisAlignment: MainAxisAlignment.spaceAround,
          ),
        ],
      ),
    );
  }
}

Widget WumpusImage([bool sus = false]) => Container(
      padding: EdgeInsets.symmetric(vertical: 16),
      margin: EdgeInsets.all(sus ? 16 : 8),
      decoration: BoxDecoration(
        border: sus ? null : Border.all(),
        color: sus ? Colors.black38 : Colors.white,
        borderRadius: BorderRadius.vertical(top: Radius.circular(32)),
      ),
      child: Center(
        child: Text(
          sus ? 'Wumpus?' : 'Wumpus',
          style:
              TextStyle(color: sus ? Colors.black : Colors.red, fontSize: 12),
          textDirection: TextDirection.ltr,
        ),
      ),
    );

Widget PitImage([bool sus = false]) => AspectRatio(
      aspectRatio: 1,
      child: Container(
        margin: EdgeInsets.all(sus ? 16 : 8),
        decoration: BoxDecoration(
          color: sus ? Colors.black38 : Colors.black,
          borderRadius: BorderRadius.circular(1000),
        ),
        child: Center(
          child: Text(
            sus ? 'Pit?' : 'Pit',
            style: TextStyle(color: Colors.white),
            textDirection: TextDirection.ltr,
          ),
        ),
      ),
    );

Widget StenchImage() => Text('Stench',
    style: TextStyle(color: Colors.green[700], fontWeight: FontWeight.bold));

Widget BreezeImage() => Text('Breeze',
    style: TextStyle(color: Colors.indigo[700], fontWeight: FontWeight.bold));

Widget AgentImage(Orientation ori) => Container(
      margin: EdgeInsets.all(8),
      decoration: BoxDecoration(
        color: Colors.green.shade400,
      ),
      child: Center(
          child: Column(
        children: [
          Text('Agent'),
          Text('<${ori.toString().substring(12)}>'),
        ],
      )),
    );

Widget Tag(String char, Color color) => Container(
      width: 16,
      height: 16,
      margin: const EdgeInsets.all(4),
      decoration: BoxDecoration(
        color: color,
        borderRadius: BorderRadius.circular(4),
      ),
      child: Text(
        char,
        style: TextStyle(fontSize: 12),
        textAlign: TextAlign.center,
      ),
    );