C++ Pathfinding Implementation...? in Design Philosophy

ID:151686
 
Aug 19 2009, 9:32 pm
We know that C++ (or any compiled code) will operate faster than something programming completely in DM.

My question is would it be more efficient to use a BYOND application of pathfinding (I.E: Theodis's) or a C++ equivalent of the same thing?

The reason I question this is because for the C++ DLL to be able to calculate the pathfinding it will need to have all of the information passed to it from dream seeker. I am wondering if the overhead for passing the information is greater than the superiority of C++ efficiency.
#1 Aug 19 2009, 9:55 pm
Theoretically, the .dll may able to access the memory space used by BYOND, if it's truly being used as a .dll (though I don't know that for sure).

Practically? That's a giant can of worms, and you aren't likely to see enough of an improvement to justify dealing with that above, say, optimizing your pathfinding routines.
#2 Aug 19 2009, 10:02 pm
My question is would it be more efficient to use a BYOND application of pathfinding (I.E: Theodis's) or a C++ equivalent of the same thing?

Yeah it certainly would be quite a bit faster.

The reason I question this is because for the C++ DLL to be able to calculate the pathfinding it will need to have all of the information passed to it from dream seeker. I am wondering if the overhead for passing the information is greater than the superiority of C++ efficiency.

And yeah that's the problem with the DLL solution since it needs the map information and some coordinates to path between and some means of returning the data. You get to use strings as parameters and get a string back. So for the sending part you either need to encode all the relevant map data in a string as well as start and end points of the path or if the map is static and doesn't change have the map file in some format that the dll can read. For the return you'd probably have a delimited string of coordinates for the path you'd have to decode.

I couldn't really see a general purpose library for this being very viable or robust. However for specialized cases you might be able to pull off some performance gains over using a library written in BYOND. A lot of work would likely be involved so best to just try what's available first and see if it gets you the performance you need before going through these kind of hoops for optimization. Not to mention using dlls prevents you from being able to host/run the game on any platform other than windows.
#3 Aug 19 2009, 10:13 pm
What's wrong with BYONDs normal pathfinding using walk_to()? It seemed fine to me...

As for the passing information... It would have to be only Starting_Point, End_Point and Density_Grid. Speed would depends how fast you will manage to make up the grid, and convert returned string to locations :)
#4 Aug 19 2009, 10:32 pm
In response to Ripiz (#3)
Ripiz wrote:
What's wrong with BYONDs normal pathfinding using walk_to()? It seemed fine to me...

Uh... Because there is NO PATHFINDING in walk_to(). Have you ever even used this proc?

All step_to does is steps towards a target. If the turf directly in the direction of your target is dense or has something dense in it, it will step around the object IF possible.

This will absolutely fail in anything that actually requires real pathfinding.

As for the passing information... It would have to be only Starting_Point, End_Point and Density_Grid. Speed would depends how fast you will manage to make up the grid, and convert returned string to locations :)

Not true... If you copied and pasting a C++ implementation of djikstra that only accepted those parameters, then sure. If you wrote your own, it could be whatever the hell you want...
#5 Aug 19 2009, 10:34 pm
In response to Garthor (#1)
Garthor wrote:
Theoretically, the .dll may able to access the memory space used by BYOND, if it's truly being used as a .dll (though I don't know that for sure).

Yea... I'm pretty sure that'd be a huge pain in the neck. Not to mention far beyond my reaches as a programmer as of now.
#6 Aug 19 2009, 10:37 pm
In response to Theodis (#2)
Theodis wrote:
My question is would it be more efficient to use a BYOND application of pathfinding (I.E: Theodis's) or a C++ equivalent of the same thing?

Yeah it certainly would be quite a bit faster.

Assuming one worked out a way to encode, parse, recode, and reparse all of the data...

After all that, do you think it would still be more efficient?
#7 Aug 19 2009, 11:18 pm
The overhead is usually not worth it. This goes for a lot of non-text heavy processing libraries, as you often end up doing data coersion equivalent to BYOND's softcode execution in terms of cost. Small gains can be made, at the cost of increased maintenance, reduced deployment scenarios and just plain bugs.
#8 Aug 19 2009, 11:22 pm
In response to Stephen001 (#7)
Stephen001 wrote:
The overhead is usually not worth it. This goes for a lot of non-text heavy processing libraries, as you often end up doing data coersion equivalent to BYOND's softcode execution in terms of cost. Small gains can be made, at the cost of increased maintenance, reduced deployment scenarios and just plain bugs.

Informative.

Thanky!
#9 Aug 20 2009, 7:36 am
Machine code that can be fed to your processor directly will always execute significantly faster than BYOND's interpreted bytecode (short of a JIT-compilation engine being integrated). Even after you find a way to encode, decode, and parse the [necessary] data, you'll likely notice some speed gains as the actual pathfinding part is typically somewhat involved; that is, you're regularly creating, maintaining, and releasing various nodes of possible paths. Probably the return from the DLL would have to be a series of coordinates at which point the object must turn in its route. In a worst-case scenario under this scheme (a zig-zag route), the parsing of the return value would probably actually outweigh doing the pathfinding in DM.

However, as Theodis said, it is a much better idea to see if you even need to do this. Optimization is your worst enemy, and should be avoided until you know that you need it, where you need it, and, specifically, what you need to do to gain the performance boost. This latter detail may not even mean using a DLL, but perhaps implementing/using a different algorithm altogether.