You could make sure you don't add duplicate elements to novaFronteira
.
There's nothing preventing this code:
for(Nodo nodoPai : nodosBase)
{
Collection<Nodo> filhos = nodoPai.gerarFilhos();
for(Nodo filho : filhos)
{
if( idsPercorridos.contains( filho.getId() ) == false )
{
novaFronteira.add( filho );
}
}
}
From adding many duplicate nodes to novaFronteira
.
If you were to add to idsPercorridos
inside the if-statement, that would prevent this from happening, and result in less steps, although, depending on exactly what your data and data structures looks like, the added running time of this call may actually make it take longer than it did originally.
If the problem is running time, you should make sure that idsPercorridos
is a TreeSet
or HashSet
, as these allow for efficient contains
calls, as opposed to ArrayList
or LinkedList
, which don't.
If this doesn't help, you could try using the A* algorithm instead, which involves adding a heuristic function to each node, which is the distance to the target - this allows us to explore the nodes closer to the target first, often resulting in less steps to get there.
A good heuristic function might be the sum of Manhattan distances between each tile and its target location.
Note that this would involve quite a few changes to your current code.