RafaelBarbosatec / a_star

Package that uses the A * algorithm to find a way to the destination through the barriers.
MIT License
17 stars 10 forks source link

need separate doneList #5

Closed Sproute777 closed 12 months ago

Sproute777 commented 12 months ago
  /// Method recursive that execute the A* algorithm
  Tile? _getTileWinner(Tile current, Tile end) {
    if (end == current) return current;
    _waitList.remove(current);
    for (final element in current.neighbors) {
      if (element.parent == null) {
        _analiseDistance(element, end, parent: current);
      }
    }
    _doneList.add(current);

    for (var n in current.neighbors) {
      if (!_doneList.contains(n)) {
        _waitList.add(n);
      }
    }
    _waitList.sort((a, b) => a.f.compareTo(b.f));

    for (final element in _waitList) {
      if (!_doneList.contains(element)) {
        final result = _getTileWinner(element, end);
        if (result != null) {
          return result;
        }
      }
    }

    return null;
  }

this search check _doneList but it is growing if search large (check all done tiles have heavy cost)

Sproute777 commented 12 months ago

maybe need add another list for separate true done list and progress done list