Pathfinding - IDA*

El algoritmo IDA* (Iterative Deepening A*) intenta encontrar el camino más corto de un punto a otro de manera más eficiente que el A* (al menos en cuanto a uso de memoria).

Aquí un buen manual de iniciación al pathfinding. Ésto a más de uno nos trae recuerdos de las asignaturas de grafos... ¡hay que refrescar esa memoria!

El pseudocódigo de dicho algoritmo es

DF-Aux(Node, Cutoff)
if f(Node) > Cutoff then return f(Node)
if solution(Node) then return Node
Min =
for each Child of Node do
Temp = DF-Aux(Child, Cutoff)
if solution(Temp) then return Temp
if Temp < Min then Min = Temp
return Min


IDA*(Root)
Cutoff = h(Root)
loop
Temp = DF-Aux(Root, Cutoff)
if solution(Temp) then return Temp
if Temp = then return failure
Cutoff = Temp

Todo ésto viene por que tengo que preparar algun tipo de IA para un proyecto en el que estoy trabajando en mis ratos libres (que aburrido parece) :D
Si alguien tiene una implementación en PHP y quiera compartirla que me comente. Probablemente en un futuro haya que preparar algun algoritmo mixto segun la situación.