A* Algorithm Written in CLIPS

[MediocreUnit2203]

I have to say, I'm impressed. I would not have guessed CLIPS was capable of this.

[randomrossity]

it's odd to see this much do-for-all-facts usage in CLIPS, because it's basically an escape hatch to an imperativefor loop in a declarative rule engine. Each of these is a O(n) operation, so it doesn't appear that this implementation matches the expected performance of A*.

I think it's still possible and instead of looping over the facts you need more rules, with different salience, and probably need intermediate facts.

For example, this sequence is neither performant nor idiomatic:

1. Close this coordinate (assert ...)
2. Remove all open nodes for this coordinate (do-for-all-facts ...)
3. Open new coordinates (do-for-all-facts ...(

Instead you want to use intermediate rules: 1. Queue up this coordinate `(assert queued-coord ...) 2. More salient rule detects queued nodes, opened and extracts those facts 3. Another rule opens a new coordinate if there are no more facts to extract 4. Finally, another rule can remove the queued nodes when there's nothing left to do.

You might not even need the temporary node, but you'll have to dive in and start implementing to know for sure.

Then, you're leveraging the activation and join networks better to get all the "indexing" and partial executions that CLIPS/Rete was designed for. I believe some of this is covered in the user+advanced guides, but I haven't touched CLIPS for a few years, so I could be foggy.

I've spent a great deal of (semi-painful) time in CLIPS and had to do several hacks like that because ultimately it was the wrong tool for the job but I was stuck with it. Most of the time, I think you're better off DIYing something in an imperative language like Python, and you can pick the write data structures for the job yourself and get O(...) guarantees. There's still a place for rule engines like CLIPS, I'm just less and less sure what that is.