Handmade Hero»Forums»Code
Livet Ersomen Strøm
163 posts
Collision detection and Pathfinding and Patents
Is it true that the A+ pathfinding algoritm is patented?

I have a question that isn't directly about pathfinding or collision detection, but about research and reuse of other algoritms.

IF you should be so lucky to discover a new way of doing things, in the course of making a game, how do you efficiently determine:

1) If it is really a new technic.

2) If you can use it, without infringing

And:

3) How can you publicize your idea, so that it can be shared by everyone else, but that you will still get credited for it, and protect it from being patented by others.

4) If your solutions build on other solutions. Does this matter at all? Say if you take inspiration from 3 other well known, and patterned technics, and invent a third way. Do you still need to credit them, and even licence their ideas in order to evolve them?

I guess I am worrying over nothing, but already I see that to complete even a simple game, takes a LOT of work. And it would be nice to have some way make sure that it isn't a waste of time.

So this thread is for sharing what you know about these issues. Is there any reason to ponder these questions for small teams?
Luca Vignaroli
10 posts
Collision detection and Pathfinding and Patents
Being in Europe I don't pay much attention to the software patent issues in the US, but I'd love to know this as well!
Gavin Williams
26 posts
Collision detection and Pathfinding and Patents
Who's going to be looking at your source code? it should probably be closed source anyway. So your intellectual property is mostly protected that way. And patents are generally for the wealthy, not for independent game devs. But the upside of that is that Sony and EA aren't going to be scouring your source code (if they could be bothered to decompile and interpret your game) for patent infringement.

Ideas, and algorithms can be patented. But as it's a legal protection, a patent is only as good as the owners legal team and determination in prosecuting or pursuing protection of their intellectual property. So A* star may be patented, but it's a common algorithm, that is often implemented from scratch, with variation. And I've never heard of anybody being pursued for using A*. So I'm pretty sure it's safe to use.

I would say that simple algorithms would be difficult to patent as they are easily and likely to be derived by almost anybody, so the development of the algorithm does not bring anything of value to the table... I actually need to look up patent rules because law is just stupid ... so in general:

Requirements for Patentability

The five primary requirements for patentability are: (1) patentable subject matter, (2) utility, (3) novelty, (4) nonobviousness, and (5) enablement.

How could A* fullfill these requirements? Tree's are an obvious way to implement navigation. You could write it using a list, but rewriting it as a tree would be an 'obvious' optimization. So even if A* is patented, I would argue that the patent did not fulfill the requirements of a patent.
Lachlan Easton
14 posts
Technically a Programmer
Collision detection and Pathfinding and Patents
I can't find any evidence to say A* is patented.

> How can you publicize your idea, so that it can be shared by
> everyone else,

Write a paper and release it to the public domain.

> but that you will still get credited for it

You'll probably need a patent.
98 posts
Collision detection and Pathfinding and Patents
Ideas, and algorithms can be patented.

Ideas can't be patented. Only a concrete representation of them that meet the patentable criteria.
Jari Komppa
41 posts / 1 project
Programmer, designer, writer, a lot of other things; http://iki.fi/sol
Collision detection and Pathfinding and Patents
Vast majority of US patents are invalid, especially if they'd follow their own rules about them (as in, patents should be understandable, results possible to be replicated by anyone working in the field, not a result of normal work in the field, not obvious to people working in the field, etc).

However, that doesn't mean anything, as mortals can't afford the legal fees anyway.
Andrew Bromage
183 posts / 1 project
Research engineer, resident maths nerd (Erdős number 3).
Collision detection and Pathfinding and Patents
Kladdehelvete
Is it true that the A+ pathfinding algoritm is patented?

The original paper on A* search was published in 1968, almost 50 years ago, and the authors of that paper did not hold a patent. So no, there is no valid patent on A* search itself.

But remember, we're just recovering from a crazy period in US patent history. It's possible that someone was granted a low-quality patent on some alleged "invention" which involves A* search somewhere who may try to assert said patent against you. Given how ubiquitous A* is, however, it doesn't seem like a huge concern.
Livet Ersomen Strøm
163 posts
Collision detection and Pathfinding and Patents
Thank to everyone for answers, I found them all constructive.