-
Yes we can
hey there,cool stuff,congrats
sorry for the rather short feedback but i just came home after a 12 work day (deadline stress..),will look into it longer on weekend =).
you mind if i add the thingy in my editor?
-
Senior Member
Thanks, I'm glad you like it. I recommend the "AI Game Programming Wisdom" book to anyone trying to do this sort of thing.
You said:
you mind if i add the thingy in my editor?
What editor? I'm sure it would be ok, I'm just curious. Thanks!
-
Yes we can
i already read several threads,articles and books (also) discussing pathfinding but thanks for the mention,i think i´ll order that one too =)
the ed is v3 of my tile ed,it features (multilayer) topdwon and iso map creation and has drawing tools for drawing (filled)rectangles/lines and circles of tiles and importing tilesets.
you can also load and save the mapoutput in any filetype (hence its a standalone app).
-
Senior Member
Sure you can add it into the editor. Send me an email and I can hook you up with what you need. Thanks!
-
Senior Member
Thank you for explaining the saved paths array. Thats very clever
Now I understand what you mean by saying the calculation of paths can take long time (I know, its not real-time, only has to be done once), you find every single path from every tile to all the other tiles.
I wonder if its worth to divide map into grids, lets say 3x3 tiles and only save the paths array for each grids center tile. This could reduce the amount of memory (size of the game) quite a lot.
-
Senior Member
this sounds so cool webgeek! I cant wait to see the article!
-
Yes we can
Originally posted by webgeek
Sure you can add it into the editor. Send me an email and I can hook you up with what you need. Thanks!
coolies,thanks,i´ll do that (but i won´t have time to get into it before weekend).
i discussed using run length encoding for the map data with pred recently,we haven´t implemented it for the mapdata yet (as our maps aren´t that big and i had to do other parts of the ed first),but wouldn´t it be possible to use run length encoding on the generated pathdata so that it shrinks dramatically in filesize?
-
Senior Member
Yup, that would work perfectly I can't tell you how much effeciency it would gain though as I don't know how many repeats would come up. Thanks!
-
Is this article still around?
Sounds like what I am looking for....
Was the source ever released for this?
-
self-portrait
Sorry for diging up an old thread
This is just amazing ^^ So incredibly fast. :O
So what you actually save in your precomputed array - is that the list of "parents" you get when running dijkstra's algorithm?
( For each node; you go through the whole list of nodes and gather information and saving this info in an array - like cost, and previous node (or parent node). Is this what you're saving? :P )
Please excuse my crappy english.. : P
-
Senior Member
I'm sorry, I don't quite understand the question?
-
self-portrait
haha, sorry, I don't completly understand what I wrote either..
But you said that your array looked something like this
path[currentPosition][endingPosition] = {x: x, y: y};
Well, how do you populate this array? I mean how does the precalculation work?
When you use for instance dijkstra's algorithm (isn't that the one you use?) you cycle through every node and sets its previousNode = currentNode..
So when you've found the path you'd have an huge array with all the nodes' previousNodes. Using these you can backtrack to the starting node and thus get your path, right?
And this is the very same array that you save If I've understood it right. It should be... :/
(of course you'd have to repeat this whole proccess for every node)
Haha, sorry, not sure if I'm making myself any clearer.. It's actually a stupid question, I'll go experiment a bit and hopefully I'll find out on my own ^^
Last edited by Kianis; 09-15-2004 at 05:05 PM.
-
Originally posted by webgeek
That's 390k of RAW data. It will compress down pretty dramatically.
Very sorry for bringing up a very old thread, but can you explain what you mean here? Is there some way to compress the data to something smaller than 390k but still make it usable for Flash ?
Thank you
-
n00b
Cool, but wouldn't it be faster using a 1 dimensional array instead? I guess its not .
EDIT:
Woohoo it is faster
here the proof:
http://www.flashdev.ch.vu/tutorials/...e/twotoone.zip
Last edited by LeechmasterB; 11-21-2004 at 09:32 PM.
I do stuff that does stuff...
J-Force
-
self-portrait
Originally posted by LeechmasterB
Cool, but wouldn't it be faster using a 1 dimensional array instead? I guess its not .
edit:
Last edited by Kianis; 08-11-2006 at 06:52 AM.
-
n00b
The more optimized things are the better it is.
So my answer would be no , if you really ask for it. If you make big games, every ms can count. Because if you have lots of things that take 10 ms it gets slower too.
Using a 1 dimensional array is almost double as fast on small arrays (50-100x50-100 elements). And still faster using big arrays 1000x1000).
I do stuff that does stuff...
J-Force
-
This works out great if the path can't be blocked. What if you have more than one object and the second object is blocking the other's way? Do you have to save ALL possible paths to get from one tile to another? I suppose a way around this is to implement a standard A* procedure that you can fall back on in this situation, but is there a different way you had in mind in this case?
-
Senior Member
I've gone ahead and updated the link to the tutorial in the first post. You can click this too if you want:
http://www.electrotank.com/junk/mike...hTutorial.html
LeechmasterB: Using 1 array might be a way to make it slightly faster (going from 5ms to like 3) but to be honest, the drop in readablity and the complexity increase in array creation doesn't really warrant the change unless you REALLY need it. This is a perfect example of premature optimization. Don't dirty things up to make things faster when you don't know if this is the problem in the first place. It's best to make it, then make it work, then make it work fast.
Plecostomus: This technique only works for STATIC maps. It's not designed to be used with dynamic maps. As such, it simply gives the shortest path. It's designed to not care if there are 10 other ways to get there, it only saves the absolute shortest. If there is no way from A to B, it will simply return nothing. Currently that's a bug in my example I never got around to fixing. I'm not sure if that answers your question though, so please let me know if I missed your point.
-
Yes, this did answer my question. I was hoping this technique was applicable in project, but do to this fallback it is not. Thanks anyways.
-
Senior Member
It sounds like you simply need to use something like A*. It's terrain aware, flexible and pretty fast. Jobe Makar's game books have an excellent A* implementation.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|