Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - PencilinHand

Pages: 1 ... 6 7 [8] 9 10 ... 28
106
DF General Discussion / Re: How big can my embarks be with my new comp?
« on: December 04, 2009, 04:03:28 pm »
Quote from: Deon on December 04, 2009, 08:53:09 am
Your processor isn't too great for DF. Even my 3200+ Athlon XP would work better, but everything else is pretty OK. I don't think that DF needs more than 500-700 Mb RAM itself.


Quote from: Asmodeous on December 04, 2009, 09:18:01 am
Actually, his T6600 has a higher clockspeed than your 3200+. It's 2.2gHz vs. the 2.0 gHz of your Athlon 64.
...

Me.

Forgive me but you have unintentionally struck on a pet peeve of mine.

Athlon XP != Athlon 64 !

Google the difference.

Sorry for the derailment.

107
DF General Discussion / Re: Fan art competition!
« on: December 03, 2009, 03:39:55 pm »
Ugh, I think a more judicious use of ye'ol censor stickers would have been more welcome.  As it is, I will cry myself to sleep tonight as that image haunts me.

To be fair to Deon, as it stands it isn't much worse than visiting a beach for the unjustifiably over confident... though he is pushing "what is acceptable" a bit I think.

108
DF General Discussion / Re: Attack of the Dreaded Hydra!!!..... corpse.
« on: December 03, 2009, 03:18:27 pm »
I once had a liaison from a neighboring civ kick the bucked before he had gotten ten tiles from the edge of the map.  There was a slight trail of blood and very annoying, as I recall.

109
DF General Discussion / Re: Anouncing The PathFinder Project
« on: December 03, 2009, 02:12:35 pm »
Quote from: CobaltKobold on November 27, 2009, 06:51:56 pm
Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.
And remember the dwarven pathfinding truism: sock.value>>elephant.cost
Quote from: shadow_slicer on November 27, 2009, 11:18:52 am
The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).

I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.
You could....take the wordsright out of my mouth.

26 directions though. When is it ever impermissible for a creature to move to where it already is? Also...I am fairly sure that flying or swimming are required to make a move to up-and-direction (without ramp, natch)
I'd suggest some manner of preclusions, but I already found a corner case I'd like preserving: swimming up waterfalls. solvable if swimming is permitted to go up.

I see why DF is loath to path fliers/swimmers right, now...for walkers, it's dead easy to see where you can go- up if on(up stair || up/down stair) && up(down stair || up/down stair) up+direction if on(ramp) && direction(wall), direction if directionIsFloored, and the downs are inverse of the ups (...actually, it won't check for the wall, as you're standing on it, leading to one-way ramps.)

I almost hate to bring this up but the thought occurred to me.

It is actually 10 directions, for a dwarf in the current implementation at least and up to 18 for a flying creature.  The reason it is 10 for a dwarf is when they are moving between z-levels at an angle(can only happen at ramps) they CAN NOT move in the direction of the ramp and stay on the same z-level.  Also, they CAN ONLY chose to go either up or down a given ramp from one direction not both.  This is because of the way that ramps are defined, they MUST have empty space on the z-level above them if they are going down. They MUST have a blocked tile on the same z-level if they are going up.

In the case of flying creatures, they can choose to either walk down the ramp or fly in the empty space on the z-level immediately above it.

To test this, construct a small wall(a 3x2 will work) and build a ramp in the middle of one of the long sides.  Then deconstruct the single wall tile that the ramp is attached to.  Then try to station someone on the wall.  The test for down ramp is equally simple, just build a wall on the z-level above the ramp and watch the guy get stuck.

For a flying creature, it could be argued that there is no need for the extra eight slanting down paths.  All pathfinding should be accomplishable for every possible creature with only 10 direction movement anyway because of the way ramps are defined in game.

Depending on the way Toady has defined the construction options and if he adds any, will depend on if more than 10 directions would be needed in the future.

110
DF General Discussion / Re: Anouncing The PathFinder Project
« on: December 02, 2009, 12:23:55 pm »
Quote from: shadow_slicer on December 02, 2009, 02:40:55 am
Trees still aren't fixed, but here's a screenshot of a path below ground.
Spoiler: Screenshot (click to show/hide)

Simply awesome!

--------
EDIT:

I have thought more about what I was proposing and have done a little research on it.  What if, instead of assuming exactly identical cost for all zones at the current hierarchy, what if A* were run one hierarchy level below what was being pathed over to generate a better approximate cost for a specific zone?

111
DF General Discussion / Re: Anouncing The PathFinder Project
« on: December 01, 2009, 04:08:36 pm »
Quote from: shadow_slicer on December 01, 2009, 02:45:14 pm
That's certainly an interesting idea. The subzone portion sound similar to the "Memory Efficient Pathfinding" paper Impaler linked to earlier.

I do have a few criticisms of your method:
Quote from: PencilinHand on November 30, 2009, 09:16:15 pm
Any given path through one zone or sub-zone to a neighboring zone or sub-zone on the same z-level will cost approximately the same **.
This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5. This means that the path found can be more than twice the optimal path length. Additionally, I don't think your method supports non-uniform path costs.

Also, you're only reducing the graph by a factor of 3. The overhead from keeping track of the new abstract graph (and its subgraphs) is likely to be larger than any gains you have from abstraction. I don't see a way to easily increase the amount of abstraction, so I'm not sure we can solve this without significant changes.

I was hoping for criticism.

It is an idea, not sure about interesting but it is an idea.  I haven't read that paper, yet, I will try to in the near future.  I may have to just break down and write the code to test it so I can get it out of my head.  At the least it will allow me to do something somewhat more productive compared to my more recent endeavors. Besides, it should be good for a few laughs if I ever finish it and make it public, so that is a bonus.

I did note that the assumption isn't always true(see the "**" note).  My argument for the assumption is that exceptions would generally be rare and relatively minor.  Generally not more than a difference of a few tiles in the whole path when the exception happens.  It is a potentially unruly assumption, off hand I can think of one case especially.   However, I think it is too important for the abstraction to work to do without it.

I think non-uniform pathcosts could be supported but would have to be generalized(so it wouldn't be exact to the tile) in a similar fashion to the zone/tile connection abstraction between hierarchy levels.  In fact, it could be used to allow a user to optimize the most glaring exceptions.

I was thinking that layering the abstracting by 3x3 for each level(suppose 3 or 4 levels?) of a hierarchy.  The memory overhead would be higher but it might significantly reduce the CPU and memory cost during the actual pathing.  If you are feeling that it would merely balloon memory cost without noticeably reducing execution cost then it is likely to be a dead end.

You didn't mention the lack of consideration for novel modes of travel, like digging/destroying obstructions, swimming, flying etc.  Or was that what you meant by the non-uniform cost comment?

For novel modes of travel, I would think that there would need to be a different method all together.

I think my posts are excessively wordy without improving clarification or communicating significantly(much like the idea, HA!).

112
DF General Discussion / Re: Future of the Fortress: List of Remaining Items
« on: December 01, 2009, 10:06:27 am »
Quote from:  The Toady one
...the squad features I wanted to go in this time are in...

 ;D

That is all.

113
DF Gameplay Questions / Re: Building a military FAST - HOW?
« on: November 30, 2009, 09:24:27 pm »
Quote from: Skorpion on November 30, 2009, 08:23:56 pm
Indeed, but that would be explainable. The dip was sudden and UNexplainable, just as winter hit.

Turned out it was three or four goblin thieves, and two melee ambush squads.
And a few goats.

The goats, of course, damn them!

114
DF General Discussion / Re: Anouncing The PathFinder Project
« on: November 30, 2009, 09:16:15 pm »
Everyone is allowed one wall of text in this thread, right?

Seriously, this is a bit dense to explain(there may be one or more MAJOR logical errors I am not seeing as well) so I am warning you to get comfortable before you start reading.



Suppose we have a 3x3 grid of tiles.

Spoiler (click to show/hide)

Continuity is guaranteed(that is that all pathable tiles are connected) within this grid if and only if the center tile is not blocked.  This should be easy to check for.

Spoiler (click to show/hide)

If the center tile is blocked, and if any two of the four cardinal points are blocked then there may be a pathable tile that is not connected within the grid.  This too should not be difficult to check for.

Spoiler (click to show/hide)

If this 3x3 grid were then split along the division to form an L and a 2x2 cube then they would be pathable within themselves.  If the geometry ever changes(suppose the center becomes unblocked) then the whole grid could be checked and merged back together.  A check for this should be relatively simple(knowing that 3x3 should start at xyz coordinates).

Of note: At most, a 3x3 grid could be divided into 4 2x2 cube(a sub-zone) with shared walls.  So sub-zones would either need to share unpathable tiles or only include pathable ones.
Spoiler (click to show/hide)

As for connected zones and subzones(preferentially).  It only be necessary to note if a zone or sub-zone is connected to its neighboring zones without having to calculate every possible connection.  All that is important is that it is or isn't connected.  So in the following example, 2 is only connected to 1 and 3 but the number of shared tiles doesn't matter.
Spoiler (click to show/hide)
Although 4 is connected to 1, 5, and 7, only 4a(the upper sub-zone) is connected to 1 and 4b(the lower subzone) is connected to 5, and 7.

All of this allows for the following assumption.  Any given path through one zone or sub-zone to a neighboring zone or sub-zone on the same z-level will cost approximately the same**.  So, each zone and subzone can be treated as a if it were an extra large tile itself.  With this A* should be able to be run at any level of the hierarchy without resolving down to the explicit per-tile path.  Resolve the path to the nearest desired zone size(suppose a 3x3 resolution) then path within each known zone that must be visit and reevaluate the overall meta-path periodically.

I haven't included stairs and ramps in this example specifically as it would confuse the attempted explanation, but they would be treated simply as more neighboring zones though the cost of moving through different z-levels would be scaled.

Under ideal circumstances, this should be able to resolve to perfect optimality.  Under less ideal circumstances I think(I haven't proven this to myself) the Delta from perfect optimality should be bound and not deviate frequently nor significantly.

A further advantage that this offers is you can then cache whatever resolution meta-path is desired.  Be it on the 3x3 or the 81x81 level.


This is, of course, assuming that the method described in this post is not only possible to implement but more CPU and memory efficient than current methods.  Admittedly, I haven't fully thought out all possibilities and shortfalls so this there is probably a major hole in this proposal.



**This isn't necessarily true. The exception(weighing a single tile sub-zone as equal to a 3x3 zone), by my reckoning, should be relatively rare and the difference should be relatively minor on the macro scale.


------------

I hope somebody smarter than me actually reads all of this and gets the idea I am trying to communicate.

Here is some thoughts on zones and subzones.
Spoiler (click to show/hide)

115
DF General Discussion / Re: Anouncing The PathFinder Project
« on: November 30, 2009, 02:58:58 pm »
Quote from: shadow_slicer on November 30, 2009, 02:07:36 pm
The current version is both worse and better than that would imply. It's worse than that because the path cache is stored directionally (though only calculated once for each direction), so all nodes have their own copy. Additionally nodes have paths to their adjacent neighbors in other zones, so there would be a total of 168 cached paths, of average length ~2.14. 

It's actually better than it seems because 1) we don't usually deal with zones smaller than 8x8, and 2) the cache is actually calculated on demand, so paths that aren't ever considered won't be calculated or stored in cache. Since the cache is filled on demand, a zone in a completely open area will probably only have to calculate a single path (if not yet cached) each call. Further this path would simply be a portion of the path non-hierarchical A* would have needed to calculate anyway.

Anyway, I'm thinking in the long run, we'll probably have to sacrifice optimality. The current implementation uses too much memory and is only twice as fast as A* for a typical load. We really need to use less memory and calculate paths faster, which is not really possible if we want to maintain optimality.

I had a feeling it was going to be something like that.

I do have an idea that might keep perfect to near perfect optimality by carefully managing and taking advantage of zone definitions.  Assuming the idea can work at all and isn't completely baseless with regards to CPU and memory considerations.  ???

Let us set that aside for the moment, though.

------

Aside from the inter/intra zone node caching, how are the paths cached?  What I mean is, are zone meta-paths cached or are the semi-explicit tile paths cached?

-------

I am sorry for these odd questions.  I have coded in C++, Java, and different flavors of Basic before but don't have the time(read as the willpower to learn more about C++) to really dig into and wrap my head around code someone else wrote.

116
DF General Discussion / Re: Anouncing The PathFinder Project
« on: November 30, 2009, 01:45:06 pm »
Quote from: shadow_slicer on November 30, 2009, 10:04:56 am
Quote from: Sunken on November 30, 2009, 09:51:49 am
Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.
In the current zoneManager implementation there are as many nodes per zone edge as there are tiles on the edge (eg. 1 node for each tile with at least one edge leaving the zone), so it is still optimal.

So then, for example, in a simple open(no obstructions, no z axis considerations) 4x4 there are 12 nodes/tiles around the edge and each node caches a path to every other node in the same zone.

11+10+9+8+7+6+5+4+3+2+1=66 cached paths with an average length of ~3 for a simple open 4x4 zone.  Is this right?

117
DF Gameplay Questions / Re: How do I attract Giant Desert Scorpions to my map?
« on: November 30, 2009, 01:32:39 pm »
Pretty much have to be lucky(a large embark helps with this).  I have only ever had one GDS come near the entrance of one of my fortresses and unfortunately he got scared off by so tame camels or something(he was quick too!).

118
DF Gameplay Questions / Re: Building a military FAST - HOW?
« on: November 30, 2009, 01:30:22 pm »
Quote from: dakenho on November 30, 2009, 01:09:44 pm
Xbow dwarfs will seem to train at archery targets and be more lethal when the goblins come back.  (not sure but it seems like they need to be off duty to do that.)

On a related note, because I saw the training time for xbow dwarfs mentioned earlier, it has been my experience that a dwarf firing at a live enemy will tend to skill up faster than one firing at a archery target.  The difference is something on the order of one half.

119
DF General Discussion / Re: Future of the Fortress: List of Remaining Items
« on: November 29, 2009, 02:57:19 pm »
Quote from: Aqizzar on November 29, 2009, 02:20:16 pm
And on that note, did anyone notice the devlog midday update?

Quote from: Toady One
One more to go, and I can finally green this section out on the list. Issues today were dwarves pitching off their uniforms whenever they had to get a bite to eat (as when they are set to not use their backpacks for food) and checking out sleep order scheduling. Last up is cleaning up various hanging issues with equipment management.

Squads done within November, as he predicted.  Rejoice.  Also, hilarious.

"Chow time!  I couldn't wait to get out of this stuffy uniform!"  What is it with dwarves and nudity right now?

I had noticed.  I am very happy that squads will be greened out on time.  The real uncertainty though lies in December.  And what is with dwarfs and nudity these days?  I suspect we will see a few comical bug reports from this once it releases.

120
DF Gameplay Questions / Re: Building a military FAST - HOW?
« on: November 29, 2009, 02:19:31 pm »
Quote from: Skorpion on November 28, 2009, 10:54:05 pm
Okay, what blocks line-of-sight without blocking wagon access?

Ask and ye shall receive.
Spoiler (click to show/hide)

Pages: 1 ... 6 7 [8] 9 10 ... 28