So you are going to store a ton of matrices on disk just for this? I'm not seeing the point.
Do yourself a favor and load up some professional editors for retail games and you will see how some of them accomplish path finding. It will give you a lot of insight into how it works.
You don't have to be rude about it. This isn't a professional game, this is an amateur 2D rpg game. I just had an idea that I thought was original and if nothign else, neat, and while incomplete I thought a group of programmers would give a better reception to some potentially new innovations but clearly I was wrong. I will restate, again, exactly what my idea accomplishes. When you pre-compile these matrices it gives you this information (I've already stated this):
Thats it!!!a) if there's a path
and (more importantly)
b) how many ways you can get from tile X to tile Y and
c) in how many steps it takes (represented by the matrix power)
Last edited by BobMcGee123; 05-29-2005 at 12:30 PM.
I'm not being rude....just do some research - and games and editors are the best place to start.
But I am stating facts here - your editor might be done processing a matrix by the end of next year for the game. Would work ok for small maps, but not large ones unless you could break it down into cells - but then you have the problem of finding which cell you are in to match the matrix on disk.
I did some timings to see how long it takes to square a matrix of various sizes using my code (these are approximate).
100 = .015 seconds
500 = 1.7 seconds
1000 = 16 seconds
1500 = 55 seconds
2000 = 132 seconds
I actually expected it to be a bit slower, but I think a more reasonable criticism is the memory footprint. a five hundred to one thousand tile map is a good size for a 2d rpg level, but to store an integer of any size, even if is just a byte, takes up a lot of space in those matrices (because you would need to store the matrix for multiple steps for it to be useful), even if you just store true/false in bit fields (a byte holding true/false information for 8 tiles, etc). So, you're probably right it won't end up being the best method, but I maintain it was an interesting idea and tonight or tomorrow I might make a simple 3D top-down pacman type game using that information and post it, just for the sake of it.
I've used the empire earth 2 editor, worldcraft editor, q3radiant, to make maps for EE2, half life, counter strike, quake3 and doom3.
Is that 500 by 500 or 500 spaces total? Oh and something seems funny because the 500 one is 113 times slower than the 100 one. You have optimization turned on?
Because its an O(N^3) , or worse, algorithm.
Anyway, the concept of preprocessed lookup tables is not something to be disregarded because you do not think it looks professional bubba
Several modern games have used preprocessed pathfinding in some way, with great success.
A hierachial approach will solve the potentially huge matrices and building times, as you pointed out yourself.
If retail games use different approaches then why wouldn't you want to use what they are since after all they are the ones making money from their efforts. I for one dont want to waste my time on classroom algos that look and sound great but offer little practicality.Anyway, the concept of preprocessed lookup tables is not something to be disregarded because you do not think it looks professional bubba
I don't care if it's professional, but the method proposed is not even rational. You act as if I've never attempted to do this in my game programming efforts.
Frankly I find your lack of respect rude. And no they dont pre-process the path - the level editor is usually what the path comes from and those nodes are placed by people, not by the computer.
In all my days of gaming I've never seen any pathfinding that I thought was really good except maybe in games like Sims and Sims 2 where you have a dynamic environment and yet the characters can still find the toilet, bathtub, etc., etc. But even that falls apart when you have multiple ways to get to the area - sometimes they will go out the kitchen door, in the front door and then to the bathroom. Not exactly brilliant.
Half life had a very good pathfinding system but again I cannot say they did not used human placed nodes or hints in the level for the NPCs to follow. Command and Conquer is ludicrous pathfinding in all generations of the game, Medieval Total War is basically find the guy and hack and slash until he is dead - all the while ingoring directional orders from you the player. SWAT 4 has horrid pathfinding problems - stairways suck, Delta Force 1, 2, BHD, Extreme and Joint Operations: Typhoon Rising as well as Escalation rely solely on waypoints - if an enemy is detected they go to alert status and well...based on pre-set variables might run towards the enemy firing - accuracy determined by the level editor, etc., etc. Flight Simulator 9 actually has some very good pathfinding for the air traffic control system as well as did Flight Unlimited 2. SWAT 2 and 3 both had horrid pathfinding as did Rainbow Six, Ghost Recon, etc. Hidden and dangerous 1 had laughable path finding.
Good examples of path finding though are believe it or not Grand Theft Auto series - very good - the cops are unreal, Mafia, Need for Speed Underground 1 and 2, etc.
That is 500 spaces (or tiles) total, I did that in debug mode but it is essentially just slowIs that 500 by 500 or 500 spaces total? Oh and something seems funny because the 500 one is 113 times slower than the 100 one. You have optimization turned on?
YeahBecause its an O(N^3) , or worse, algorithm.
Bubba you very clearly know what you are talking about, but you also very clearly have an elitist attitude. WE ARE AMATEURS AND ARE TRYING NEW THINGS. I sincerely hope that your own personal projects are particularly advanced and that you can back up your arrogantness. It is true my idea is not great, but I just wish you had said something along the lines of "well bud I am a fellow game programmer and I know how hard it is to innovate new ideas, but your algorithm isn't that great because of these following reasons" instead of "do yourself a favor" and blah blah blah.
I already have the shame of putting too much time into an idea that won't work...you could at least show some respect by being nice about it.
Last edited by BobMcGee123; 05-29-2005 at 04:48 PM.
I'm not sure if you meant that retail games do not use look up tables, but if you did you are mistaken Bubba. If you mean that you probably won't find the proposed algorithm used, you're probably right. Although it is a pretty interesting algorithm in my opinion. Instead of logic, you're using pure math! I am quite interested to hear the results of your pac man demo BobMcGee.Quote:
Anyway, the concept of preprocessed lookup tables is not something to be disregarded because you do not think it looks professional bubba
If retail games use different approaches then why wouldn't you want to use what they are since after all they are the ones making money from their efforts. I for one dont want to waste my time on classroom algos that look and sound great but offer little practicality.
You're very right about how node meshes are created for 3D games, however in 2D you rarely need a node mesh. Especially if it's a tile lay out (it's already a node mesh by some definitions).
Not to start a war, but the AI in GTA is a complete hack. They spawn around corners so you can't see them, and ram into you lol.
Skorman I really appreciate the encouragement. I will fiddle around with my idea a little bit more. The pre processing doesn't matter to me because the results can just be saved to a file, but I will see if I can think of any way to perhaps cut down the memory footprint and make sure that any calculations that do need to be done realtime can be done reasonably quickly. i might make my pacman thing 3D so it might take a little bit longer, and it won't be a game per se just a mechanism for showing the functionality of the path finding. If you have any ideas feel free to share
They do, but not when you are chasing another car or another car of thugs is chasing you. Those cars are AI objects and they are chasing you. The cops, however, do cheat and just re-spawn at the nearest intersection.Not to start a war, but the AI in GTA is a complete hack. They spawn around corners so you can't see them, and ram into you lol.
Mafia had very good pathfinding and I'd like to know how they did it. The cops would respawn but it was not as evident as GTA. The cops would follow you literally for mile after mile through winding streets, etc, etc. It was very good. Somehow I think they tracked the streets you took and simply followed the same route. I don't remember if they actually tried to take a crossroad to cut you off. Now that would be a very good algorithm but I wouldn't want to to code it.
And no I'm not saying they don't use look-up tables, but I am saying this is overkill for what needs to be done at this time.
And for Bob:
To say I'm an elitist when you don't even know me is really not a good thing. I've helped a lot of people here and made a lot of friends, supplied all kinds of code, screenshots, algos, etc, etc. I hardly think elitist is the word for it. My advice for when you code algos is keep it simple stupid - anything else is either going to be a mess or cause the whole thing to never get done.
So basically use the easiest thing that gets the job done well, perhaps not the best job, but it still works.
Last edited by VirtualAce; 05-29-2005 at 05:47 PM.
Well then I'm sorry, I was angry.
sorry for the delayed reply, the link MrWizard posted a page back was perfect for what i wanted, it even had 2 examples and its surprisingly fast... about 2 ms for a 70x70 tiled map (i only needed 1 for about 10x10 to 15x15)
once again, thanks to everyone for all the help
edit: wow.. only 4 or 5 posts in this topic are actually related to my question
Last edited by X PaYnE X; 05-30-2005 at 01:50 AM.
