Brainstorming - trying to rework something and hit a wall

[toolkitxx]

Hello fellow coders,

i am actually in need of some inspirational help here. My brain simply refuses to spit something decent out so i decided to get some outside help from you.

Situation: I have a loose set of nodes identified by unique IDs. The player can move between these nodes but usually only between nodes that are adjacent to each other. The nodes themselves dont know about their neighbours but include code to display a 'move to' action to the player in the UI.

Problem: Moving between nodes is done via executing a move command which in return moves the player from node a to b and also advances time. Travel times are varied but have been simplified already to 5 simple different ones. Currently each single move is its own static block of code as nodes are not located on an underlying grid thus there is no direct relation among them.

Solution i am trying to achieve (with least impact on current code):
While the player is supposed to move from node to node as it is currently implemented I want to give the player the choice to 'fast travel' via a map like feature. This would require some kind of pathing system that would build a list of nodes between the start and the destination and add up all travel times to ensure proper time advancing. But since there is currently no relation between each node i need to create something simple and easy. My first thought was that of a simple DNS like structure where each node gets the information added which direct neighbours are around but that wouldnt be enough as there is travel time too.

Any ideas are welcome - this is more or less a brainstorming where there are no bad ideas

 

[doodee]

I would just create structure { neighbour ID, travel time } and assign a list of those to each node.
Then a pathfinding function would also add travel times accordingly.
Hope this helps.

 

[toolkitxx]

@doodee Hm - that could actually work. More like a regular waypoint system. Which also solves my secondary problem of nodes that basically are on the same position in a 2d grid but not on a 3d grid.

 

[toolkitxx]

hm - looks like i am back to creating a Breadth First Search then under any circumstances. Had hoped there was some simpler way but maybe this isnt that bad actually. It would probably allow me to change the current 'move' code to be much more automatic too.

 

[anne O'nymous]

So, basically what you want is a

You must be registered to see the links

that will work over a

You must be registered to see the links

.




Old algorithms are always the best, they have this smell of dust that made them unique.

 

[toolkitxx]

So, basically what you want is a

You must be registered to see the links

that will work over a

You must be registered to see the links

.
Old algorithms are always the best, they have this smell of dust that made them unique.

I actually tried to avoid that to begin with as most of the code for moving around etc was already done and wouldnt easily support a-star algorithm. I had just cleaned up all my nodes of stuff and thought i could use some kind of domain/dns routing system but that failed big time.
Usually there is no need for pathing but if i have to do it for the fast travel i might as well change my current way of moving the player as it could open up for a few extra choices in navigation like 'go home' , 'go to work' etc

P.S: maybe i should explain what i mean with domain system: All my nodes are basically somewhere in a 2d grid but some of them are sub-nodes to those and thus not really 2d anymore but basically 3d like rooms of a house etc

 

[anne O'nymous]

I actually tried to avoid that to begin with as most of the code for moving around etc was already done and wouldnt easily support a-star algorithm.

So instead of using it as effective search algorithm, can you use it as internal component of the nodes ? Something like that (in pure-pseudo code) :

node:
   searchNode = Null
   searchWeight = 9999
   searchPath = Null

   [...]

   // node is the ID (see below) of the destination node.
   weightTo( node ):
     // Links is the array (of whatever) of all the nodes linked to this one.
     // ID is whatever you want identifying a node (object reference, ID string, rank in a list, etc.).
     if node present in self.Links   return ( [ self.ID, node ], 1)
     if self.searchNode is node    return ( self.searchPath, self.searchWeight )

     self.searchNode = node
     self.searchPath = null
     self.searchWeight = 99999999

     for n = all nodes in self.Links
        ( p, w ) = n.weightTo( node )
        if w < self.searchWeight
           self.searchWeight = w
           self.searchPath = p

     self.searchPath = [ self.ID + self.searchPath ]
     self.searchWeight += 1
     return ( self.searchPath, self.searchWeight )

So the only thing you'll have to do is interrogate the actual node.

 ( path, weight) = actualNode.weightTo( destNode )

And path will be an array of all the nodes, from the actual to the destination one, for the shortest path to destNode. In practice it's a search algorithm, but you use it like a simple method call.

 

[toolkitxx]

@anne O'nymous I am not dealing with an OO language - but the basic idea could actually work and be used for both fast and regular travel when i do as you suggest and use the search as function/method. Nice input!

 

[toolkitxx]

Just as additional info why this is making my head so much: The node layer is supposed to be easily accessible for modders /authors - so it has to be as simple as possible. Functions less so as they will be in the system layer.

 

[toolkitxx]

@anne O'nymous You gave me the right idea - thanks a lot. I played a bit with different versions of those algorithms and i think i am going for some

You must be registered to see the links

stuff as storing all paths might be the easiest with regards to my problem.

 

[Saki_Sliz]

For this fast travel, which players be looking at a list of locations or nodes to go to, or will players have a type of map come up? I ask because I know in some older games where they couldn't afford to run a fancy algorithm in game, they instead used the player to do the pathfinding, without the player realizing it too much. Basically, if you have a map, the cursor starts where the player is at, and as the player moves the cursor to their goal destination, an arrow extends out from the starting position and folows the cursor, so if I go up up right up right down, the arrow would have that shape, with the arrow representing the path. since players would be able to see the arrow, they would start to plan their paths that make sense. An example would be the path system in the Fire Emblem games.

But that is assuming you don't have a ton of nodes and only want to be able to fast travel to few very specific nodes that are far apart, if that is the case, I can see why using a simplified map or list would be more desirable, and in that case you would want to do the pathfinding under the hood.

But it sounds like from the code above, that you are trying to solve the sales man problem, which is still an impossible problem in modern computer coding. If you want your code to be modder friendly, that implies to me that you are trying to make as much of the behaviors as the code autonomous as possible, avoiding hard coding in behaviors. Because, you could represent the node network as 2D, worst case you would have it be 3D or maybe even 4D, but if you wanted to find the shortest distance you may need to use something like a gradient map and integrate over it to eventually find the destination, it would be like neural network convolutions, but this has the same issues as many sales man problem solutions do.

the issue with the code anne showed above is it is prone to short distance dependancy loops, and short branching, meaning that unless each node understands where it is in the network of nodes, the short term solution they would bring could cause the search to not be able to terminate correctly. having nodes understand where there are in the network is why I brought up describing the network as 2D,3D,4D, not that they depend on space, but if you could prepresnt the network without any path crossing one another, than a gradient-based search may work. if you know the node system is 2D and that no path's will cross, then in that case a code solution would probably be the best and easiest to implement, but unless I put some much more serious thought into it, I don't know exactly how such a solution would exist code wise. As you may have noticed, I am taking a much more mathier approach to this since I hear this more in math class then coding class, since coder's are not expected to work on this since even the best minds of today haven't figured out this type of problem yet, but it is a useful topic to talk about for math major's. since I am still an undegrad, I may have to talk to my professor to get a better idea about these kind of problems and what math is used for them. It's been like 3 years but I very distincly remember having 2 weeks about this topic.

if you can find a solution, let us know, you might earn a nobel prize XD

 

[toolkitxx]

For this fast travel, which players be looking at a list of locations or nodes to go to, or will players have a type of map come up? I ask because I know in some older games where they couldn't afford to run a fancy algorithm in game, they instead used the player to do the pathfinding, without the player realizing it too much. Basically, if you have a map, the cursor starts where the player is at, and as the player moves the cursor to their goal destination, an arrow extends out from the starting position and folows the cursor, so if I go up up right up right down, the arrow would have that shape, with the arrow representing the path. since players would be able to see the arrow, they would start to plan their paths that make sense. An example would be the path system in the Fire Emblem games.

But that is assuming you don't have a ton of nodes and only want to be able to fast travel to few very specific nodes that are far apart, if that is the case, I can see why using a simplified map or list would be more desirable, and in that case you would want to do the pathfinding under the hood.

But it sounds like from the code above, that you are trying to solve the sales man problem, which is still an impossible problem in modern computer coding. If you want your code to be modder friendly, that implies to me that you are trying to make as much of the behaviours as the code autonomous as possible, avoiding hard coding in behaviours. Because, you could represent the node network as 2D, worst case you would have it be 3D or maybe even 4D, but if you wanted to find the shortest distance you may need to use something like a gradient map and integrate over it to eventually find the destination, it would be like neural network convolutions, but this has the same issues as many sales man problem solutions do.

the issue with the code anne showed above is it is prone to short distance dependancy loops, and short branching, meaning that unless each node understands where it is in the network of nodes, the short term solution they would bring could cause the search to not be able to terminate correctly. having nodes understand where there are in the network is why I brought up describing the network as 2D,3D,4D, not that they depend on space, but if you could prepresnt the network without any path crossing one another, than a gradient-based search may work. if you know the node system is 2D and that no path's will cross, then in that case a code solution would probably be the best and easiest to implement, but unless I put some much more serious thought into it, I don't know exactly how such a solution would exist code wise. As you may have noticed, I am taking a much more mathier approach to this since I hear this more in math class then coding class, since coder's are not expected to work on this since even the best minds of today haven't figured out this type of problem yet, but it is a useful topic to talk about for math major's. since I am still an undegrad, I may have to talk to my professor to get a better idea about these kind of problems and what math is used for them. It's been like 3 years but I very distincly remember having 2 weeks about this topic.

if you can find a solution, let us know, you might earn a nobel prize XD

Would love to solve that riddle once for all but that isnt going to happen

In my 'world' it is actually not really about the shortest path at all but about a path. I face the problem that the world actually uses time for activities. Some happen 'under the hood' and modders/authors will never really touch them. Others like moving from A to B are always player initiated for their avatar and while being executed the 'hidden under the hood' stuff gets done as well (NPCs get moved around according to their schedules). Both parts use the same objects if you will - the nodes are one of them. For the player the node is an actual place in the world thus prone to be touched by modders/authors. From experience i know that players sometimes just want to 'jump' to a certain place instead of actually travelling there the 'normal' way. Goal is simply to offer this kind of travel without corrupting the base line of the mechanics which means time advances and stuff happens during this time.

P.S. I completely agree with your point of the complexity but every complex thing can be solved by breaking it down to smaller pieces. For me that might mean breaking down my nodes into 'regions' and applying the algorithm on several layers instead of all at the same time.

 

[Saki_Sliz]

Then perhaps a question of time may be more appropriate means to find a solution. How is time expressed in your game? How does time move? In one project, I simplified things to the point of a point and click game, with time only progressing when the player does something (interact or move scenes) and I kept the time system simple, and characters would move only between these events, but never during (this way you could run around to catch up to a npc to interact with them). while on the far other end would be realtime simulation. it sounds like you are using nodes to simplify the enviorment, but would simplifying time also help? maybe you already pointed out how you plan to use time and I missed that part.

The issue with the complexity of the sales man problem isn't that it can't be solved, rather, its that no matter what methods are used, the more nodes added, the longer it takes to calculate (exponentially so) a solution. one trick you could use to make it so that these calculations are easy durning game play, is to generate a look up table. generating the look up table is where most of the work happens, and this must be done by the developer, usually, before the game is shipped. using a l.u.t. the code is rather simple, generating a lut is up to you. for example most car engines have computers, those computers are not powerful enough to do the math and simulation needed to adjust the engine parameters accordingly, so instead these computers have many look up tables and their performance is dependant on how many look up's the computer can do per second.

using a lut may seem clunky at time, having a big table or array, but an image is just that, and I don't think having one lut as big as a 4K image is all that detrimental if I think about modern computers, as well as it is unlikely to have as many nodes an possible combinations as there are pixels in a 4k image. but the code is super fast in game, input the pointer for the start node, and teh pointer for the exit node, and the array tells you the value of time elapsed, with the time previously calculated by another algorithem (which could search multiple paths for the optimal route). so going about it this way could mean any algorithm you use should be good, so long as modders are ok with rebuilding the look up table any time they make a change to the nodes. And this way, if you have tons of npc's moving around, figuring out time for each with the look up solution shouldn't take more than 3 clock cycles per npc, making this a fairly linear operation per npc count which isn't the best but isn't bad either.

 

[toolkitxx]

Time is already simplified due to the nature of the underlying engine. Time only advances after some kind of player interaction which also means a players action triggers the moment where the processing of everything happens. This is why a-star isnt really feasible or necessary as its about 'a path' not really the shortest. The salesman problem doesnt apply neither here as the user chooses one and only one location to fast travel to at any given time.
But time advancement has more implications at the time a player makes the choice of fast travel. Everything else in the world is supposed to advance according to the time used - which is why i need to have the actual path and the time it takes to feed all the other 'under the hood' stuff.

Floyd-Warshall solves this pretty nicely - at least for what i was trying to achieve as the algorithm delivers all travel times of all node pairs which reside in a simple array afterwards.

P.S. That also means adding or changing nodes by a modder/author doesnt require any further knowledge of how the travel etc actually works. Which is one of my major concerns while i code this. Any modder/author will know the neighbours and can assign from a simple set of travel times - that's all they need then.

 

[Saki_Sliz]

Ah, good to hear! I'll have to look into this solution by floyd, it may be useful to be familiar with it for future projects.

 

[toolkitxx]

Ah, good to hear! I'll have to look into this solution by floyd, it may be useful to be familiar with it for future projects.

Check the link in the earlier post for it - you can step by step play interactively with the algorithm on that website. Opened my eyes quite a bit

 

[Saki_Sliz]

Hey, yeah, that's pretty cool someone put that page together, thank's for linking it!