Jump to content

  • Log In with Google      Sign In   
  • Create Account

KnolanCross

Member Since 29 Sep 2012
Offline Last Active Jun 01 2016 07:38 AM

Posts I've Made

In Topic: C vs Java (+ frameworks), Engines...?

13 January 2016 - 06:43 AM

 

Just an extra, in case you decide to use libgdx (which, AFAIK is the most well developed open source java engine), you should take a look at overlap2d. It is a scene editor that integrates very well with libdgx.

 

http://overlap2d.com/


In Topic: Caching paths

14 December 2015 - 09:11 AM

I don't know any articles about caching A* path finder results.

 

(I assume you are working in the case of optimal paths.)

Pondering about it, the biggest issue is probably how to decide your path finding results have become invalid. I don't see an easy answer to that question.

Knowing when your result is still valid is probably easier. I would define "valid" as "if you run the computation again, you will get the same answer" (where "same" is still complicated).

 

In free open space, I would expect that a computed path stays valid  if reachability of all nodes that you explored in the search is the same (ie it stays free open space), and all traversal costs from one node to the next in the set explored nodes is the same (ie not suddenly making it more or less attractive to reach a node).

The reasoning here is that in your path search, you explore a number of nodes while looking for the shortest path.  If you do that computation again, and reachability and traversal costs of all nodes that you explore have not changed, you should end up with the exact same set of nodes, and the same path. "Same" is a bit tricky here, you can have several distinct routes of equal length, and due to the order of the nodes in the data structures, and order of considering traversals, I would expect you could end up with a different route of equal length. (Shorter cannot happen I think, since the path you got the first time was already the shortest given the costs, and longer cannot happen since the path you derived the first time still exists, and would then be better.)

 

So in free open space, if you store the set of explored nodes (ie all nodes in the open and closed lists) along with the path, and costs of reaching each of these nodes does not change, I think your path is still valid (modulo alternative routes of equal length).

 

If you add blockages to the equation (ie some nodes cannot be entered) it gets more complicated. A new blockage at the current path makes the path invalid (duh smile.png ).

A new blockage in the set explored nodes but not on the path seems harmless at first sight. Reasoning is that the node with the new blockage is no longer reachable, but that doesn't affect the path, since the blockage was not on the path. In addition, nodes reached from the node that is now blocked, cannot be reached from that node any more. Maybe they can be reached through some other node, but that path is not going to be shorter (or the original path would not have gone through the now blocked node). Thus if anything happens to the explored nodes off the path, their distances get bigger rather than smaller. Your set of explored nodes for the path may get smaller thus. This makes sense, adding new blockages generally means you're blocking off some options.

Adding new blockages outside the set explored nodes does not give new (shorter) paths.

 

Removing blockages is quite complicated. Note that blocked nodes are never in the open or closed lists, since you cannot reach the node at all. If the removed blockage is neighbour of a closed node, the blockage prevented all paths through that now unblocked node. Some of those newly available paths to the destination may be shorter than the path you currently have. You could check that, I think, by extending the path from the closed neighbours to the now unblocked node. If the sum of the real distance to the now unblocked node and its estimate is less than the current length of the path to the destination, a path through the now unblocked node may indeed be shorter (ie your current path is now invalid). If the sum is equal, a path may exist, but it is not shorter (since your estimate is never above the real distance). It may have equal length though, which leads you back to the "same path" discussion above.

 

I think removing a blockage from a node that only has neighbouring explored nodes in the open list is harmless. Nodes in the open list have equal or higher costs than the real path, you add some travel costs from the neighbour to the now unblocked node, so its total cost is never going to be lower than the path you have now.

 

 

If you have blockages, I think a reasonable approximation could be

- New blockage on the shortest path breaks the path

- New blockage elsewhere should not cause any change to the shortest path

- Removed blockage of a neighbour node of the explored nodes invalidates the path. (The discussion above was more precise, but it requires knowledge of real distances from the source to all explored nodes, which is probably too costly.)

 

I didn't consider changes in costs for traveling to a neighbour, but it seems to me you could perhaps apply similar reasoning as with blockages.

 

Thank you for your answer, albert.

 

I actually read an article that uses a very similar strategy of what you describe (reusing the already computed parts of a path), but my focus is to reuse the paths itself. It is quite hard to find because caches are very limited, as you stated, they need to be clear at changes and most algorithms work on a very limited set of rules (there seems to be no answer that fits all the constraints).


In Topic: Looking for a free 2D engine

01 December 2015 - 10:30 AM

Hello,

As the title suggests I am looking for a suitable game engine. We are 3 programmers that have never made a game before but now want to create a complete game. The game will have: C++, 2D graphics, top down view, Real time action and a story component.
Sadly I failed to find a real engine which uses C++ and still allows modifying components to better fit into our game.
Thank you in advance for helping us.

 

Can you give a little more context of what you need?

 

I have been using orx (http://orx-project.org/) for 3 years, it is written on C, but has a C++ shell as well (called Scroll) and brings a lot to the table such as support for animations, sound, particle effects, FX* and time tracks**.

It is core idea is to have objects described on ini files and create/control them via source.

It has a small, but very active community (which now I am a part of) and questions on the forum/gitter are answered pretty fast.

 

 

* Basically it changes an attribute of an object for a given period of time, very useful for small effects. For instance, you can use it to change an object alpha, which  causes a blinking effect, that serves as an enemy death effect.

** A scripted series of time based events.


In Topic: SF government/race types

25 September 2015 - 07:52 AM

Theocracy

 

If they are a religious organization maybe you could use caliphate?

 

I was going to suggest hive, but I was too late =p


In Topic: ENET peer list?

17 September 2015 - 01:45 PM

enet_host_broadcast will send a packet to the local network for everyone to receive if they're listening to it. I don't think that's what the OP wants.

The ENetPeer is the main connection object representing the "other end," so I imagine this is valid until such time that the connection goes away. I don't know what kind of notification you get when it becomes invalid, though.

 

Are you sure? I just tested here (server running on NY based VM, clients running on my machine).

This:

packet = enet_packet_create(buffer, strlen(buffer)+1, 0);
enet_host_broadcast(server, 1, packet);

And this:

for (i = 0; i <  ipeerCount; i++) {
    if (&server->peers[i] != event.peer) {
        packet = enet_packet_create(buffer, strlen(buffer)+1, 0);
        enet_peer_send(&server->peers[i], 0, packet);
        enet_host_flush(server);
    }
}

Both worked for the clients (I can paste the outputs here).

 

PS: I ommited the buffer value initialization.


PARTNERS