AI Algorithms on GPU,
Members - Reputation: 132
Posted 11 August 2005 - 08:45 PM
- A* it's for finding path...
- Algorithm to find path a 'matrix' way ? Perhaps this
1) Build a matrix A, where A(i,j) = 0 if we can reach node(j) from node(i) in one step
2) For the matrix multiplications, replace + by max, and * by +
3) Compute A^n : A(i,j) will give you the distance you need to reach node(j) from node(i), if this distance is < n
- A^n is cheap to compute. Example
A^7 = (A^4) * (A^3)
A^4 = (A^2) * (A^2)
A^3 = (A^2) * A
A^2 = A * A
4 multiplications instead of 7, log2(n) instead of n ;)
- It could help for a pathfinding, I'am not sure it's very interesting (complexity, efficency)
Anyway, with a special matrix (path on a square grid as example), I'am nearly sure there is some tricks to reduce computations.
Members - Reputation: 100
Posted 11 August 2005 - 10:52 PM
Original post by Sneftel
Mark my words: within five years, we'll see multi-core processing on Intel and AMD processors. Get ready for that.
Hmm, you do know Athlon X2 and Pentium 4D are already available? ;-) I've had SMP dual and quad machines for years.