← Back to branch summary

~ubuntu-branches/ubuntu/precise/triplea/precise

« back to all changes in this revision

Viewing changes to src/games/strategy/engine/data/CompositeRouteFinder.java

  • Committer: Package Import Robot
  • Author(s): Scott Howard
  • Date: 2011-11-11 21:40:11 UTC
  • Revision ID: package-import@ubuntu.com-20111111214011-sehf2rwat36o2xqf
Tags: upstream-1.3.2.2
Import upstream version 1.3.2.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/games/strategy/engine/data/CompositeRouteFinder.java
 
1
/*
 
2
 * This program is free software; you can redistribute it and/or modify
 
3
 * it under the terms of the GNU General Public License as published by
 
4
 * the Free Software Foundation; either version 2 of the License, or
 
5
 * (at your option) any later version.
 
6
 * This program is distributed in the hope that it will be useful,
 
7
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
8
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
9
 * GNU General Public License for more details.
 
10
 * You should have received a copy of the GNU General Public License
 
11
 * along with this program; if not, write to the Free Software
 
12
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
13
 */
 
14
 
 
15
package games.strategy.engine.data;
 
16
 
 
17
import games.strategy.triplea.delegate.Matches;
 
18
import games.strategy.util.CompositeMatchOr;
 
19
import games.strategy.util.Match;
 
20
 
 
21
import java.util.ArrayList;
 
22
import java.util.Collection;
 
23
import java.util.Collections;
 
24
import java.util.HashMap;
 
25
import java.util.HashSet;
 
26
import java.util.List;
 
27
import java.util.logging.Logger;
 
28
 
 
29
public class CompositeRouteFinder
 
30
{
 
31
    private final static Logger s_logger = Logger.getLogger(CompositeRouteFinder.class.getName());
 
32
    public static Logger GetStaticLogger()
 
33
    {
 
34
        return s_logger;
 
35
    }
 
36
    private final GameMap m_map;
 
37
    private final HashMap<Match<Territory>, Integer> m_matches;
 
38
 
 
39
    /**
 
40
     * This class can find composite routes between two territories.
 
41
     *
 
42
     * Example set of matches: [Friendly Land, score: 1] [Enemy Land, score: 2] [Neutral Land, score = 4]
 
43
     *
 
44
     * With this example set, an 8 length friendly route is considered equal in score to a 4 length enemy route and a 2 length neutral route.
 
45
     * This is because the friendly route score is 1/2 of the enemy route score and 1/4 of the neutral route score.
 
46
     *
 
47
     * Note that you can choose whatever scores you want, and that the matches can mix and match with each other in any way.
 
48
     *
 
49
     * @param map - Game map found through <gamedata>.getMap()
 
50
     * @param matches - Set of matches and scores. The lower a match is scored, the more favorable it is.
 
51
     */
 
52
    public CompositeRouteFinder(GameMap map, HashMap<Match<Territory>, Integer> matches)
 
53
    {
 
54
        m_map = map;
 
55
        m_matches = matches;
 
56
        s_logger.finer("Initializing CompositeRouteFinderClass...");
 
57
    }
 
58
    private HashSet<Territory> ToHashSet(Collection<Territory> ters)
 
59
    {
 
60
        HashSet<Territory> result = new HashSet<Territory>();
 
61
        for(Territory ter : ters)
 
62
            result.add(ter);
 
63
        return result;
 
64
    }
 
65
    public Route findRoute(Territory start, Territory end)
 
66
    {
 
67
        HashSet<Territory> allMatchingTers = ToHashSet(Match.getMatches(m_map.getTerritories(), new CompositeMatchOr<Territory>(m_matches.keySet())));
 
68
 
 
69
        HashMap<Territory, Integer> terScoreMap = CreateScoreMap(allMatchingTers, start);
 
70
        HashMap<Territory, Integer> routeScoreMap = new HashMap<Territory, Integer>();
 
71
        int bestRouteToEndScore = Integer.MAX_VALUE;
 
72
 
 
73
        HashMap<Territory, Territory> previous = new HashMap<Territory, Territory>();
 
74
        List<Territory> routeLeadersToProcess = new ArrayList<Territory>();
 
75
        for (Territory ter : m_map.getNeighbors(start, Matches.territoryIsInList(allMatchingTers)))
 
76
        {
 
77
            int routeScore = terScoreMap.get(start) + terScoreMap.get(ter);
 
78
            routeScoreMap.put(ter, routeScore);
 
79
            routeLeadersToProcess.add(ter);
 
80
            previous.put(ter, start);
 
81
        }
 
82
        while(routeLeadersToProcess.size() > 0)
 
83
        {
 
84
            List<Territory> newLeaders = new ArrayList<Territory>();
 
85
            for(Territory oldLeader : routeLeadersToProcess)
 
86
            {
 
87
                for (Territory ter : m_map.getNeighbors(oldLeader, Matches.territoryIsInList(allMatchingTers)))
 
88
                {
 
89
                    int routeScore = routeScoreMap.get(oldLeader) + terScoreMap.get(ter);
 
90
                    if(routeLeadersToProcess.contains(ter) || ter.equals(start)) //If we're bumping into one of the current route leaders or the start
 
91
                        continue;
 
92
                    if(previous.containsKey(ter)) //If we're bumping into an existing route
 
93
                    {
 
94
                        if(routeScore >= routeScoreMap.get(ter)) //If the already existing route route is better or the same
 
95
                            continue;
 
96
                    }
 
97
                    if (bestRouteToEndScore <= routeScore)
 
98
                        continue; //Ignore this route leader, as we know we already have a better route
 
99
                    routeScoreMap.put(ter, routeScore);
 
100
                    newLeaders.add(ter);
 
101
                    previous.put(ter, oldLeader);
 
102
                    if (ter.equals(end))
 
103
                    {
 
104
                        if(routeScore < bestRouteToEndScore)
 
105
                            bestRouteToEndScore = routeScore;
 
106
                    }
 
107
                }
 
108
            }
 
109
            routeLeadersToProcess = newLeaders;
 
110
        }
 
111
        if(bestRouteToEndScore == Integer.MAX_VALUE)
 
112
            return null;
 
113
        return AssembleRoute(start, end, previous);
 
114
    }
 
115
    private Route AssembleRoute(Territory start, Territory end, HashMap<Territory, Territory> previous)
 
116
    {
 
117
        List<Territory> routeTers = new ArrayList<Territory>();
 
118
        Territory curTer = end;
 
119
        while(previous.containsKey(curTer))
 
120
        {
 
121
            routeTers.add(curTer);
 
122
            curTer = previous.get(curTer);
 
123
        }
 
124
        routeTers.add(start);
 
125
        Collections.reverse(routeTers);
 
126
        return new Route(routeTers);
 
127
    }
 
128
    private HashMap<Territory, Integer> CreateScoreMap(Collection<Territory> ters, Territory startTer)
 
129
    {
 
130
        HashMap<Territory, Integer> result = new HashMap<Territory, Integer>();
 
131
        for (Territory ter : m_map.getTerritories())
 
132
        {
 
133
            result.put(ter, GetTerScore(ter));
 
134
        }
 
135
        return result;
 
136
    }
 
137
    /*
 
138
     * Returns the score of the best match that matches this territory
 
139
     */
 
140
    private Integer GetTerScore(Territory ter)
 
141
    {
 
142
        int bestMatchingScore = Integer.MAX_VALUE;
 
143
        for(Match<Territory> match : m_matches.keySet())
 
144
        {
 
145
            int score = m_matches.get(match);
 
146
            if(score < bestMatchingScore) //If this is a 'better' match
 
147
            {
 
148
                if(match.match(ter))
 
149
                {
 
150
                    bestMatchingScore = score;
 
151
                }
 
152
            }
 
153
        }
 
154
        return bestMatchingScore;
 
155
    }
 
156
}