Thread: OpenGL Matrices

You're really going to use that algo Bob? I thought you would use depth-first or some form of stack system we discussed to find paths, or even a node-based system

My algorithm is node based. The nodes are placed in the map by map makers. The map gets loaded in, and a ray trace line of sight interaction is performed to get the initial 1's and 0's of the first matrix, then, using my code, it raises the matrices to powers to find the connectivity matrices (then saves the data to file). I am familiar with the other methods (I was at the time of that discussion). I have rejected every other method of pathfinding because mine is faster realtime (you do not have to find the whole path in order to move to the next node along the path, and it never has to back up or retry anything) and I knocked down the compilation time so the compile process is roughly O(n) (it calculates the 'matrices' using data structures that aren't really matrices, and doesn't really do any math to do it).

I'm especially proud of it because it's very difficult to get something even remotely original to work, and have it be fast enough and use a low enough amount of memory to be acceptable. After I implemented it, I had found a math topic and floyd's all pairs algorithm that is sort of like what I had implemented, but I have yet to see anything else like this in modern games (I wouldn't be surprised if it already is in use though ).

The problem with my demo that I posted before was that I was having the computer randomly generate a maze, and they came out looking retarded (no offense shamino).

Well since I've not had calculus in school and am totally self taught.....it looks to me as if I learned linear algebra before calculus

Yeah, you did. I believe a lot of both theory and practical knowledge is healthy, but gaining practical knowledge through experience is a much more difficult process than taking a university class. Even in theory classes a lot of it is just trusting the processor that the ideas being presented work (as opposed to grappling with the ideas yourself, in whatever arena). Then, once you'ge got a healthy vocabulary of ideas that you accept as valid, you then build upon more abstract ones (bull........ that piles up upon bull........ and always works in the arena of textbooks).

I had actually failed my first calculus 3 test, with a 55, because I had gone and done it too quickly. I went in to talk to the professor and solved a problem he could not do in class. Then I started talking to him about some of my game programming topics, he realized exactly where I stood in terms of my knowledge, and he raised my test grade by 30 points (even though I technically didn't deserve it). True story (look up Jerry Farlow on umaine's website).

offense? did I miss something ?

http://math.fullerton.edu/mathews/n2...MatrixMod.html

It has pseudo-code for how to do gaussian-jordan elimination, and an example of how to use that to find the inverse matrix.

I seem to recall having to write a program to find the inverse of a matrix in september... but that was in september. And it could have just been the matrix transpose. If I find my program (and it looks semi-useful) I'll post it


EDIT: Ran across this in the 'links' thread.

http://www.geocities.com/SiliconVall.../matrices.html

~Mith

>>OK, you guys, stop arguing.

I was actually somewhat defending you. And he started it

Razzle frazzle frigga fraggle!

*goes to mumble back in his sleep*

I love this message board.

Well in D3D you can invert a matrix by doing this:

Code:

D3DXMATRIX matInv;

//Create translation matrix as source for testing inverse
D3DXMATRIX matTrans;
//100 on x, 200 on y, and 300 on z
D3DXMatrixTranslation(&matTrans,100.0f,200.0f,300.0f);


D3DXMatrixInverse(&matInv,NULL,&matSource);

Gotta love the D3DX library.

The NULL is where the determinant variable goes, if you have one which in this case I do not.

And yes, Bob, it is very hard to create something that has not been done before (and better?) and is equally as efficient and useful. Most game programming problems usually end up using similar algos to solve them. Perhaps this is because games have to be both fast and efficient so there isn't much room for error.

And now as far as pathfinding it is good to have an algorithm that can do this well, but sometimes I feel it is not. Don't give the AI more information than a normal human player would have at any one point. Sometimes it's not bad to take the wrong path. If we were all running through a maze, it would be very hard to find each other without some type of communication system. If Bob and I were driving somewhere and he didn't know how to get there, if Bob loses sight of me......guess what, he either is screwed, must call me and tell me to slow down and wait, or he can ask for directions which will probably land him nowhere close to where he wants to be. Sometimes game AI is too smart. They have too much knowledge and as such, it makes the game much harder than the same situation would be in real life. Now when you make your AI fallible then the player doesn't mind not being found or shot at every 5 minutes no matter where they go.
Having superhuman AI really sucks, but having complete idiots also sucks. A happy medium is needed.

Too smart: Half Life 1, GTA: Vice City (cheaters actually - police spawn at nearest intersection).
Too dumb: Rainbow Six, No One Lives Forever 1

Just about right: Mafia.

>> GTA: Vice City (cheaters actually - police spawn at nearest intersection).

I just started playing that again and the level of AI cheating is thoroughly peeing me off. I'd like to know how the engine works, with so much going on at once. Well I guess not much is happening where you aren't in the map, but you know what I mean.

Don't give the AI more information than a normal human player would have at any one point. Sometimes it's not bad to take the wrong path

I understand what you are saying. It's just as easy to take the wrong path in my implementation as it is with any of 'the others.' In my opinion, to get pathfinding to really work in a realistic manner, we'd have to ditch all of the current constructs that we have for pathfinding. No A*, none of my implementation, or breadth/depth first etc. Instead, you'd have to implement a low-level cognitive model that recognizes geometry in the world and can perceive it in relation to what it already recognizes (memory and recollection), and in relation to the last time it saw a bad guy. This would be too difficult and inefficient for a simple computer game such as mine. But, what you've been talking about is faking it so that it seems 'just right,' as in Mafia (and I do remember half life 1's pathfinding to be too perfect.)

Granted, I'm still experimenting and learning, and we'll see how good it really works when I've got a playable demo to release. In fact, I'll probably have a release just to play with the pathfinding.

Cheap isn't bad...the only thing that's bad is something that doesn't work.