OptimalBarrierPath

package com.godlinggame.mapmodel;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import com.badlogic.gdx.utils.Array;


public class OptimalBarrierPath extends OptimalPath
{
HashMap<MapLocation, Array<distance>> distances = null;


  public OptimalBarrierPath( Map map )
  {
    super( map );
    setMap( map );
  }


  @Override
  public void setMap( Map map )
  {
    super.setMap( map );
    distances = new HashMap<MapLocation, Array<distance>>();
  }


  @Override
  public double stepCost( MapLocation ml, double barrierWeight )
  {
    if (null == distances) return Map.OutOfBounds;

  Array<distance> da = distances.get( ml );

    if (null == da || da.size < 1) return Map.OutOfBounds;

  double best = Map.OutOfBounds;

    for ( distance d : da )
    {
    double cost = d.cost( barrierWeight );

      if (best > cost)
        best = cost;
    }

    return best;
  }


  @Override
  public void clearPath() { distances.clear(); }
  @Override
  public void addGoalPosition( MapLocation add )
  {
    addDistance( add, new distance( 0.0, 0.0 ));
  }


  @Override
  public void recomputePath()
  {
    recomputePath( distances.keySet() );
  }


  protected void recomputePath( Set<MapLocation> start )
  {
  HashSet<MapLocation> newwork, work;

    work = new HashSet<MapLocation>();
    newwork = new HashSet<MapLocation>();
    work.addAll( start );

    while(!work.isEmpty())
    {
    Iterator<MapLocation> it = work.iterator();

      while( it.hasNext() )
      {
      MapLocation ml = it.next(), newloc;
      Array<distance> d = getDistances( ml );

        newloc = ml.move( 1, 0 );
        if (addPaths( d, newloc )) newwork.add( newloc );
        newloc = ml.move( -1, 0 );
        if (addPaths( d, newloc )) newwork.add( newloc );
        newloc = ml.move( 0, 1 );
        if (addPaths( d, newloc )) newwork.add( newloc );
        newloc = ml.move( 0, -1 );
        if (addPaths( d, newloc )) newwork.add( newloc );
      }

      work = newwork;
      newwork = new HashSet<MapLocation>();
    }
  }


  private boolean addPaths( Array<distance> begin, MapLocation add )
  {
  boolean added = false;
  double barrier = map.getBarrierAt( add );

    if (barrier != Map.OutOfBounds)
      for( distance d : begin )
      {
        if (addDistance( add, d.add( 1.0, barrier )))
          added = true;
      }

    return added;
  }


  private Array<distance> getDistances( MapLocation ml )
  {
    return distances.get( ml );
  }


  private boolean addDistance( MapLocation ml, distance d )
  {
  Array<distance> alld = getDistances( ml );

    if (null == alld)
    {
      alld = new Array<distance>( false, 16 );
      alld.add( d );
      distances.put( ml,  alld );

      return true;
    }

  boolean add = false;

    for (int i=0; i<alld.size; i++)
    {
    distance old = alld.get( i );

      if (old.move <= d.move && old.barrier <= d.barrier) return false;
      if (old.move > d.move || old.barrier > d.barrier)
      {
        if (old.move >= d.move && old.barrier >= d.barrier)
        {
          alld.set( i, d );
          return true;
        }

        add = true;
      }
    }

    if (add)
      alld.add( d );

    return add;
  }
}


class distance
{
final double move, barrier;


  distance( double move, double barrier )
  {
    this.move = move;
    this.barrier = barrier;
  }


  double cost( double barrierWeight )
  {
    return move + barrier * barrierWeight;
  }


  distance add( double move, double barrier )
  {
    return new distance( move + this.move, barrier + this.barrier );
  }


  public boolean equals( Object o )
  {
    if (this == o) return true;

    if (o instanceof distance)
    {
    distance d = (distance) o;

      return move == d.move && barrier == d.barrier;
    }

    return false;
  }


  public String toString() { return " d("+move+", "+barrier+")"; }
}