Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[malloc]

I see what you guys mean now. Yeah, I guess it makes sense that you loose out on a lot by taking these 3+ years out of my working life. But the situation is quite a bit different here, it's hard to get anywhere without a education.

[MaximumZero]

I know that here, a "2 year degree" (which takes 3+ years,) is mandatory, if you want a job doing anything touching computers. After this, I'll probably be a junior code monkey for the next 3-5 years while working on a Bachelor's. Then I might be able to call myself a professional programmer. Maybe.

[Willfor]

Being a form of engineering, the following applies to programming too:
"When told that work is work and spare time is not for engineering I am concerned that the candidate's world view is not really that of a successful engineer."
http://www.analog.com/en/all-operational-amplifiers-op-amps/operational-amplifiers-op-amps/products/raq_make_do_issue61/resources/faq.html

Being in the process of an education in audio engineering, I'm extremely grateful for this link.

[Mego]

You know what...I'll probably just write a tutorial on writing makefiles...they're incredibly useful when you have more than three or four files to compile together.

Requesting this. Makefiles are the kind of magic I never really got good at. Probably because I'm not too great at bash scripting.

[dreadmullet]

Here's an animation I made that shows my pathfinding algorithm at work. It's standard A*, which I believe is exactly the algorithm Dwarf Fortress uses. It runs on a seperate thread, too. Take that Toady One!

Spoiler (click to show/hide)

[Willfor]

Take that Toady One!

Exactly how many map data variables are being accessed and changed by other processes while your pathfinding algorithm is running?

[dreadmullet]

It's all concurrent. I don't see how that's a problem, though. The worst that can happen is it tries to path past a very recently locked door or something, then realize it's locked when it periodically checks if the path is still valid. I would love to be proven wrong.

It's all very simple at the moment. I understand that Dwarf Fortress is many times more complex than my current engine. I just think it's fun to compare myself to the toad.

[Valid_Dark]

Here's an animation I made that shows my pathfinding algorithm at work. It's standard A*, which I believe is exactly the algorithm Dwarf Fortress uses. It runs on a seperate thread, too. Take that Toady One!

Spoiler (click to show/hide)

I've never done any work with pathfinding, and I found this interesting,  Is this really the basic background of a pathfinder?  I expected something a bit cleaner or without so much unneeded work being done,  I can understand basically whats going on here, and I never attempted to think of a way of doing it myself, it just seems like a lot more than I would have thought.

[MorleyDev]

I've never done any work with pathfinding, and I found this interesting,  Is this really the basic background of a pathfinder?  I expected something a bit cleaner or without so much unneeded work being done,  I can understand basically whats going on here, and I never attempted to think of a way of doing it myself, it just seems like a lot more than I would have thought.

This is a pretty standard flat implementation of A*. They may be optimisations in certain situations that can be made, but they usually require either the graph being optimised for them or certain assumptions be made. For example, you could treat the overall room structure as a graph and use A* to find your way from room to room, and then use A* again to find your way through each room.

A* is rather efficient as far as path finding goes. It's based on Dijkstra's Algorithm, which checks every node in the graph but is guaranteed to return the shortest path. A* on the other hand, is guaranteed to return a path. It won't always return the shortest path, but the path it returns is reasonably decent and it's faster than Dijkstra's as it doesn't check every node.

You might be able to optimise DF by making it detect 'rooms' as they are made, and then use them for path-finding.

As for threading, DF may be better optimised in terms of concurrency by spreading the search across all the cores. That's usually the easier, less optimal, way of shoe-horning concurrency into a project not designed for it.

[Nadaka]

Here's an animation I made that shows my pathfinding algorithm at work. It's standard A*, which I believe is exactly the algorithm Dwarf Fortress uses. It runs on a seperate thread, too. Take that Toady One!

Spoiler (click to show/hide)

It is possible that your seeking algorithm isn't as efficient as it could be. I note that it only seeks in the 8 cardinal directions towards the destination. If it encounters a partial obstruction, but can still move in a direction that places it closer to the destination it might save quite a bit of searching under most use cases.

Code: [Select]

XXXXXXXXXXXXXXXX
X          B   X
XXXXXXXXXXXXXX X
X   .          X
X  .           X
X .            X
XA             X
XXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXX
X          B   X
XXXXXXXXXXXXXX X
X   ........   X
X  .           X
X .            X
XA             X
XXXXXXXXXXXXXXXX


[Valid_Dark]

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?

[Nadaka]

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?

Correct, I probably need to clarify. It only seeks in the cardinal direction most directly towards the destination until that direction is blocked and it then stops and starts flooding, even if it can still travel in a straight line that brings it closer to the destination.

[dreadmullet]

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?

Correct, I probably need to clarify. It only seeks in the cardinal direction most directly towards the destination until that direction is blocked and it then stops and starts flooding, even if it can still travel in a straight line that brings it closer to the destination.

That's just how A* works. To my knowledge, it's the best algorithm that will always produce the shortest path in an efficient way.

I can change one variable that will kind of make it do what you describe. If I increase the heuristic multiplier (hMult) from 1 to 10, it will be more aggressive in testing nodes that are closer to the destination. In your example, it would be faster, since it would branch out into less nodes. However, consider this example:

Code: [Select]

XXXXXXXXXXXXXXXXXX
X          B     X
XXXXXXXXXXXXXXXX X
X              X X
X              X X
X              X X
XA               X
XXXXXXXXXXXXXXXXXX

With hMult = 1 and hMult = 10, it will probably test the same amount of nodes each. More importantly, if hMult is greater than 1, it may generate a suboptimal path. I suspect in this case it would start to move toward B, and then move back into the optimal route. This article has some excellent animations.

[Wolfy]

I've done some things but nothing majoir, TBH I can never for the life of me, use what I learn, I can tell you what evrything dose and if you ask me what I think you need, I can get you something that works, but if I'm doing it I draw blanks.

[MadocComadrin]

I note that it only seeks in the 8 cardinal directions towards the destination.

In a 2d world, aren't there only 8 cardinal directions?

In a 2d grid world, it depends on the shape used to make a grid. In a square grid, you have 4 directions that can take you from a center of one square to the center of another in 1 square's length. Any other direction takes a longer "step." A regular-octagon-based grid has 8 of these directions.

Spoiler (click to show/hide)

Technically, there are only ever 4 cardinal directions by definition, each 90 degrees apart.