[QUOTE=Deco Da Man;33316434]Progressive A*. The use of a heuristic function makes it viable in even the most demanding situations.
Unfortunately, it doesn't work well with portal-style systems, if that's a requirement.[/QUOTE]
Why wouldn't it work with portals? You'd have to create a node connecting both portals with a "cost" that is the same as a normal tile if you catch my drift.
[QUOTE=DrLuke2;33317801]Why wouldn't it work with portals? You'd have to create a node connecting both portals with a "cost" that is the same as a normal tile if you catch my drift.[/QUOTE]
The issue is probably the heuristic. It's probably difficult to come up with a good heuristic in situations like that. It should still work though.
Algorithms without heuristics don't care about the node's position in 3D space. Dijkstra's, for example, would work exactly the same regardless.
Just a guess.
[QUOTE=Jookia;33317259]Desura's build system doesn't impress me.[/QUOTE]
What I find terrifying is that the developer later says he mixes a* b, a * b, and a *b for pointers, dereferencing, and multiplication, and doesn't stick to one actual style for any one of them.
:suicide:
[QUOTE=ROBO_DONUT;33317956]The issue is probably the heuristic. It's probably difficult to come up with a good heuristic in situations like that. It should still work though.
Algorithms without heuristics don't care about the node's position in 3D space. Dijkstra's, for example, would work exactly the same regardless.
Just a guess.[/QUOTE]
Of course, the heuristic will at first assume it's a longer way, but won't it eventually find the shortest route?
[QUOTE=DrLuke2;33317801]Why wouldn't it work with portals? You'd have to create a node connecting both portals with a "cost" that is the same as a normal tile if you catch my drift.[/QUOTE]
It would find a path, but it wouldn't necessarily find the optimal path unless your heuristic function took into account the fact that a portal might shorten the path.
[editline]17th November 2011[/editline]
[QUOTE=DrLuke2;33318054]Of course, the heuristic will at first assume it's a longer way, but won't it eventually find the shortest route?[/QUOTE]
No, an important property of the heuristic is that it shouldn't overestimate the path.
[QUOTE=DrLuke2;33318054]Of course, the heuristic will at first assume it's a longer way, but won't it eventually find the shortest route?[/QUOTE]
I don't think so.
If the destination is 10 meters in one direction and the portal to the destination is 5 meters in the opposite direction, A* may never reach the portal at all.
[QUOTE=Chandler;33318029]What I find terrifying is that the developer later says he mixes a* b, a * b, and a *b for pointers, dereferencing, and multiplication, and doesn't stick to one actual style for any one of them.
:suicide:[/QUOTE]
What
The only method is *pointer, *dereference and multi * plication
[editline]17th November 2011[/editline]
I [B]know[/B] it's based on opinion just thought of expressing mine. Don't care about the way it's represented. Don't start a flamewar. Just rate disagree. Please. :ohdear:
I was thinking you could simply build of list of possible direct line paths with respect to portals and choose the shortest one for your heuristic, however the problem is that you are assuming you must go through the portal that has the shortest distances, when in reality, that portal may be behind a maze and therefore not optimal to pass through.
I guess you could run the algorithm with the best heuristic, and then, if the result is drastically larger than the expected value, rerun the algorithm with the next best heuristic.
[QUOTE=esalaka;33318155]What
The only method is *pointer, *dereference and multi * plication
[editline]17th November 2011[/editline]
I [B]know[/B] it's based on opinion just thought of expressing mine. Don't care about the way it's represented. Don't start a flamewar. Just rate disagree. Please. :ohdear:[/QUOTE]
Except that that's the [i]right way[/i], since unary * is right-associative.
Consider the statements:
[code]
int* a, b, c;
int *a, b, c;
[/code]
'a' is a pointer to an int, while 'b' and 'c' are just plain old integers. This is more apparent in the latter case.
To clarify, I mean it's 'the right way' as in the most sensible way, not the intolerant 'imma fail you cuz you whitespace different' right way.
[QUOTE=ROBO_DONUT;33318148]I don't think so.
If the destination is 10 meters in one direction and the portal to the destination is 5 meters in the opposite direction, A* may never reach the portal at all.[/QUOTE]
How about have a node in both ends of a portal, and when finding the distance from that "portal node" to any other node on the graph, you choose the min of two ends' distances to the other node?
I.e. actual node A in one end of portal, actual node B in other end, destination C.
On the graph, you have special node AB instead, and dist(AB,C) = min(dist(A,C),dist(B,C)) ?
I'm not sure how to quantify it yet, but it almost sounds like this problem is recursive; a two-tiered pathfinding problem. First you consider your position, the destination, and the portals as nodes, and [b]below[/b] that you do the "normal" pathfinding.
[editline]17th November 2011[/editline]
automerge
[QUOTE=Nikita;33318250]How about have a node in both ends of a portal, and when finding the distance from that "portal node" to any other node on the graph, you choose the min of two ends' distances to the other node?
I.e. actual node A in one end of portal, actual node B in other end, destination C.
On the graph, you have special node AB instead, and dist(AB,C) = min(dist(A,C),dist(B,C)) ?[/QUOTE]
Because that doesn't help?
At least not within the context of A*
Actually, I guess that could work with a few modifications.
If A is the node being considered, B is the destination, and C/D are portals then:
d = min(dist(A, B), dist(A, C) + dist(D, B), dist(A, D) + dist(C, B))
If you have more than one set of portals, though, it becomes unwieldy.
[QUOTE=ROBO_DONUT;33318214]Except that that's the [i]right way[/i], since unary * is right-associative.
Consider the statements:
[code]
int* a, b, c;
int *a, b, c;
[/code]
'a' is a pointer to an int, while 'b' and 'c' are just plain old integers. This is more apparent in the latter case.
To clarify, I mean it's 'the right way' as in the most sensible way, not the intolerant 'imma fail you cuz you whitespace different' right way.[/QUOTE]
Oh. I didn't even remember. It just felt somewhat right to do it like this when I started making my style less, um, whitespace-y. (I used to have spaces everywhere. For example I used to write something like (void *)(ptrA + 1) as ( void * ) ( ptrA + 1 ) and it got completely ridiculous with function calls at times.)
Here's what I'm thinking:
You have a map with portals:
(green is starting position, red is destination, pink is set of portals, orange another set of portals)
[img]http://dl.dropbox.com/u/39921754/portal_pathfinding_1.png[/img]
In order to solve the pathfinding, you create a second tier, so this second tier of nodes looks like this:
[img]http://dl.dropbox.com/u/39921754/portal_pathfinding_2.png[/img]
^Because the portals break your heuristic into pieces, you need to represent each piece of the heuristic into a node.
This is how you would measure your tier two heuristic.
[img]http://dl.dropbox.com/u/39921754/portal_pathfinding_3.png[/img]
So, in this example, you'd of course first try to go through pink, but the tier one pathfinding would quickly reveal that the real cost of this path is greater than the direct heuristic, and it would switch the path to the direct green to red path. This would again turn out longer than the heuristic of going through the orange portal, and then you'd arrive at your destination with the optimal path.
To be clear, you'd measure the real cost of the tier paths by the aggregate real cost of the underlying tier one path.
[editline]17th November 2011[/editline]
I just realized that missing from this, unlike standard A*, is an overall heuristic for tier 2. I think the idea still works however, but if anyone wants to improve upon this idea or point out why it won't work, be my guest.
[QUOTE=ROBO_DONUT;33318214]Except that that's the [i]right way[/i], since unary * is right-associative.
Consider the statements:
[code]
int* a, b, c;
int *a, b, c;
[/code]
'a' is a pointer to an int, while 'b' and 'c' are just plain old integers. This is more apparent in the latter case.
To clarify, I mean it's 'the right way' as in the most sensible way, not the intolerant 'imma fail you cuz you whitespace different' right way.[/QUOTE]
Oh wow. I wondered why my int* a, b; statements didn't work. Do references work the same way?
[QUOTE=Lexic;33319013]Oh wow. I wondered why my int* a, b; statements didn't work. Do references work the same way?[/QUOTE]
Probably.
Also, that's one of the things mentioned so often everywhere I wonder why you hadn't heard of it.
Anyone use unity? We were working on a voice controlled iOS game that was going nowhere, so I shut it down and we're selling the tech we created for it.
[url]http://www.facepunchstudios.com/unity/pitchpoll/[/url]
keep in mind that only applies to C/C++
in C#, int* a, b works as you would expect it to work
[QUOTE=icantread49;33319061]
in C#, int* a, b works as you would expect it to work[/QUOTE]
How you expect it to work is subjective. The C standard defines it in the manner it's done in C and thus a lot of C and C++ programmers have grown to expect it to work the way it does.
Maybe the C# way is more intuitive for most, though.
But everything in C# is a pointer anyways :v:
[QUOTE=Yogurt;33319186]But everything in C# is a pointer anyways :v:[/QUOTE]
It's references, not pointers. And not everything is one. It's very important to know when you are working in C#.
Basic types are copied when passed around, class instances are passed by reference and struct instances are considered value types are are also copied.
This makes a difference especially when you are testing for equality.
[QUOTE=garry;33319057]Anyone use unity? We were working on a voice controlled iOS game that was going nowhere, so I shut it down and we're selling the tech we created for it.
[url]http://www.facepunchstudios.com/unity/pitchpoll/[/url][/QUOTE]
Haha, loved the "fuck.." at the end
Working on a simple sand toy for school;
[img]http://i55.tinypic.com/5u47pv.png[/img]
okay fuck everything, i'm rolling my own GUI :v: wasted an entire day yesterday
Sorry, you need to Log In to post a reply to this thread.
