Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Variants

Reply
 
Thread Tools Display Modes
Old December 3, 2012, 20:41   #31
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,057
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to Magnate
Quote:
Originally Posted by Mikko Lehtinen View Post
It's not necessarily just for fine-tuning rarities. I've crafted a very simple but efficient rarity system for a future version of Mist. I'm going to have only six different rarity lines for melee weapons, and perhaps for devices too:

Code:
A:0/55:12/30:24/0
A:0/40:24/10:36/10:60/0
A:0/5:12/40:60/0
A:0/0:12/5:24/40:60/10
A:12/0:36/40:60/20
A:36/0:60/70
As long as there are as many melee weapons of each rarity, melee weapons as a group will always be just as common, but your chances of finding better weapons increases slightly every time you take the stairs down.
You'll be able to replicate that in Pyrel using the "allocations" member of each object's definition.

I've cut and pasted my stream of consciousness to http://bitbucket.org/derakon/pyrel/w...m%20generation where it now precedes the more low-level code-related stuff. I was of course intending to write a 'proper' wiki entry on item generation when Pyrel 'went public' on rephial or its own site or wherever. Glad it was helpful.

@Derakon: I assume you'll be copying the instructional parts of previous dev log entries to said wiki at some point?
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila
Magnate is offline   Reply With Quote
Old December 3, 2012, 21:19   #32
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,916
Derakon is on a distinguished road
Quote:
Originally Posted by Magnate View Post
@Derakon: I assume you'll be copying the instructional parts of previous dev log entries to said wiki at some point?
Good idea!

(They'll probably need some tweaking since they're "this is what I plan to do", not "this is what was done", but they'll make a good starting point)
Derakon is online now   Reply With Quote
Old December 4, 2012, 00:55   #33
Patashu
Knight
 
Patashu's Avatar
 
Join Date: Jan 2008
Posts: 526
Patashu is on a distinguished road
Ok, calc is now an order of magnitude slower than eval for common cases (although I would like to have it much faster!)

http://pastebin.com/U2iRBxqX

using timeit with 10000 repeats in the python interpreter:
Code:
calc("1")  0.0418998227178
eval("1")  0.0812901957397
1  0.000138238181535
calc("1+1")  0.576610918564
eval("1+1")  0.0973678084556
1+1  0.000208210600249
calc("1+2-3*4/5*6-7+8")  1.62794541196
eval("1+2-3*4/5*6-7+8")  0.184303583337
1+2-3*4/5*6-7+8  0.00143016787479
Outstanding issues:
1) How should it take in variables - should it take an object with them, a dictionary with them? Should it discard them after one calculation or only when you explicitly tell it? Should the calculator itself be an object, such that you garbage collect it when you no longer need its variables?
2) Should it always return a float? (It could try to determine if it is an int and return that instead. Or just return the string and let the caller decide.)
3) User defined functions?
4) Faster!
__________________
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu

Last edited by Patashu; December 5, 2012 at 00:44.
Patashu is offline   Reply With Quote
Old December 19, 2012, 05:25   #34
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,916
Derakon is on a distinguished road
Quick note, folks -- Aerdan's IRC logs seem to be offline, so I can't guarantee I'll see anything you say to me. Might be best to do our asynchronous communication on the forum for the time being.

Magnate -- I see your pull requests, I'll try to get to them tonight but if I don't, tomorrow's looking pretty busy unfortunately.
Derakon is online now   Reply With Quote
Old February 8, 2013, 20:24   #35
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,916
Derakon is on a distinguished road
Okay, let's start picking up where we left off. Uh, which is where, exactly? I know Magnate is working on item generation and Fizzix is working on dungeon generation. I don't know if anyone else is tackling a major feature at the moment. Checking the To-Do List, it looks like the top things are:

1) Porting in effects from Vanilla (spell, item, and monster effects).
2) Limiting player knowledge (limited LOS; unidentified and partially-identified items)
3) Making creatures smarter (pathfinding)

I'd like to start on adding effects in. Some of these are straightforward -- anything that applies a (de)buff, for example, can be done right now with no further modification to the code. However, many spells require what Vanilla calls "projections" where a projectile needs to move across terrain. I believe the same system is also used to determine what has LOS on what. Both of these will need some efficient way to determine if a given tile is obstructed or not. And that in turn ties into pathfinding. So basically all three of these major features are related at some level.

In Vanilla, determining if a tile is obstructed is fairly straightforward: there's one terrain type and one monster per tile, and they either obstruct (sight/projection/movement) or they don't. Pyrel doesn't have that kind of simplicity -- there can be any number of Things in a tile (terrain, creatures, and more), and we might potentially want any number of them to act as an obstruction, so we'll need to be clever if we want calculations to be fast.

What these kinds of algorithms want to operate on is a 2D array of booleans, that indicates if a cell is "open" (visible / accessible / etc.) or "closed" (obstructed). Call it an "accessibility array". So we have a function that accepts a list of Things in the tile and decides if the tile is open or closed. Where we run into trouble is when we try to do this every tick for every cell for every thing that needs to check accessibility. Imagine calculating LOS for 95 orcs when the player opens a pit. Every orc would need to check if the other 94 orcs block its view (not to mention the walls and the player) -- a naive algorithm would perform horribly. What we need, I believe, is a cache.

The cache will remember, for a given function, the status of the function's accessibility array. All of the orcs use the same sight function (being able to see through creatures but not walls), so they all use the same logic to determine if a given tile is blocked or not. Thus we need only compute accessibility once for each tile, instead of once for each tile for each orc; the result can be compiled into an array and passed to the LOS computation function (which would need to run once for each orc). Moreover, so long as the contents of the tile do not change, we don't have to recompute its accessibility. We can use the same "dirty tile" logic we use in drawing the game map to determine which tiles need to have their accessibility re-checked (i.e. to flush cache entries). NB currently dirty tiles are tracked by the artists; that should be moved into the GameMap, probably.

So what this looks like, in practice, is that we have two sets of functions. The first set determines tile accessibility, and the second set makes use of the accessibility arrays. For example:
Code:
First set
1) Can see through tile
2) Can walk through tile (normal)
3) Can walk through tile (wallwalker)

Second set
A) Compute LOS
B) Pathfind to player
C) Fire projectile
Each function in the second set begins by requesting a specific accessibility array from the GameMap. It then does whatever it needs to do with that array (e.g. compute a path, or determine where a projectile stops). The first time the accessibility array is requested, it has to be computed for the entire map; from then on, incremental updates can be used instead. This should work well for most use cases I can think of; it's not ideal for functions that are used rarely (e.g. projectiles that can pass through glass walls), but those are used rarely, so their impact shouldn't be heavily felt.

When a new map is generated, every tile is dirty, of course. We can track accessibility functions that were used commonly on the previous level, and pre-emptively compute their accessibility arrays as part of new map generation, in a multithreaded manner so that they don't contribute excessively to level generation time.

Potentially we can let the second-set functions request subsets of the accessibility array. That would then save on the amount of dirty cells that would need to be recomputed -- you wouldn't have to do the entire map. I think this mostly only makes sense for projectile calculations, though, since those have a known maximum range (dependent on the projectile function). I don't know how much time it would save in practice, since at the very most there's only going to be a couple hundred or so dirty cells per player turn, right?

Does this all seem reasonable? Unreasonable? Am I overlooking anything?
Derakon is online now   Reply With Quote
Old February 8, 2013, 21:08   #36
LostTemplar
Knight
 
Join Date: Aug 2009
Posts: 670
LostTemplar is on a distinguished road
Maybe just have one value per tile, that determine it's accessiblity status (not just boolean, but also not too genral, e.g. lava is different from floor, etc.) Which is computed when and only when the given tile is modifyed, not when someone wants to look thru it.
LostTemplar is offline   Reply With Quote
Old February 8, 2013, 21:46   #37
jdh
Rookie
 
Join Date: Jan 2013
Posts: 10
jdh is on a distinguished road
Quote:
Originally Posted by Derakon View Post
What these kinds of algorithms want to operate on is a 2D array of booleans, that indicates if a cell is "open" (visible / accessible / etc.) or "closed" (obstructed). Call it an "accessibility array". So we have a function that accepts a list of Things in the tile and decides if the tile is open or closed. Where we run into trouble is when we try to do this every tick for every cell for every thing that needs to check accessibility. Imagine calculating LOS for 95 orcs when the player opens a pit. Every orc would need to check if the other 94 orcs block its view (not to mention the walls and the player) -- a naive algorithm would perform horribly. What we need, I believe, is a cache.

The cache will remember, for a given function, the status of the function's accessibility array. All of the orcs use the same sight function (being able to see through creatures but not walls), so they all use the same logic to determine if a given tile is blocked or not. Thus we need only compute accessibility once for each tile, instead of once for each tile for each orc;
Two more complicated examples come to mind:

1. Opacity: you might be able to see through a few orcs if you are only a few orcs back in the mob, but a crowd of 100? And what if you have mist, rain, smoke or fog? It would be cool if it could accumulate and have stages of effect: you see poorly 3 or 4 tiles away, hallucinations or mirages 4-10 steps away and nothing further than that...

2. Directionality: suppose you would like to have one-way mirrors that let you see into rooms but not out, or perhaps camouflaged entrances which monsters see out of but are difficult to see into?
jdh is offline   Reply With Quote
Old February 8, 2013, 21:59   #38
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,916
Derakon is on a distinguished road
Quote:
Originally Posted by jdh View Post
1. Opacity: you might be able to see through a few orcs if you are only a few orcs back in the mob, but a crowd of 100? And what if you have mist, rain, smoke or fog? It would be cool if it could accumulate and have stages of effect: you see poorly 3 or 4 tiles away, hallucinations or mirages 4-10 steps away and nothing further than that...
There's no reason you couldn't have an array of floating point numbers instead of an array of booleans. Then 0 represents completely unobstructed, 1 completely obstructed, and anything in-between is partially obstructed.

Quote:
2. Directionality: suppose you would like to have one-way mirrors that let you see into rooms but not out, or perhaps camouflaged entrances which monsters see out of but are difficult to see into?
This would need to be handled on a per-invocation basis (as opposed to when the accessibility array is updated), since you can't have directionality without having a source and target. The way I'd do it would be to have a value (e.g. None) that indicates that the tile needs to be handled specially. So while trying to get LOS, the function checks that tile, sees that it requires special handling, and manually checks the tile contents.

Quote:
Originally Posted by LostTemplar
Maybe just have one value per tile, that determine it's accessiblity status (not just boolean, but also not too genral, e.g. lava is different from floor, etc.) Which is computed when and only when the given tile is modifyed, not when someone wants to look thru it.
It sounds like you're suggesting I hardcode a set of kinds of accessibility into the game engine? But that means modifying the engine if we come up with new ways of seeing / projecting. For example, if we want to add X-ray vision and lead walls, then we'd have to modify the base engine instead of just adding a new pair of functions for accessibility and augmented LOS. Feel free to correct me if I'm misunderstanding you.
Derakon is online now   Reply With Quote
Old February 9, 2013, 00:18   #39
jdh
Rookie
 
Join Date: Jan 2013
Posts: 10
jdh is on a distinguished road
Quote:
Originally Posted by Derakon View Post
This would need to be handled on a per-invocation basis (as opposed to when the accessibility array is updated), since you can't have directionality without having a source and target. The way I'd do it would be to have a value (e.g. None) that indicates that the tile needs to be handled specially. So while trying to get LOS, the function checks that tile, sees that it requires special handling, and manually checks the tile contents.
I would think you could implement this as a sort of directed graph, with a cost for traveling from each tile to each adjacent tile: e.g., if you have tiles in each of the 8 keypad directions, there would be a cost for moving to each. (I don't know whether you're contemplating extensibility to other geometries.) Your cache would store costs for entire paths, but each path greater than 1 would have several other paths as subsets: cost(a,d) for a -> b -> c -> d would check cache[a,d], then fall back to cost(a,c)+cost(c,d). This may be excessive cleverness and I don't know how you would apply it to things other than line projections (such as Sil's noise concept), but I wouldn't think it would be too many more than 95 calculations for 95 orcs checking whether they can see the player.
jdh is offline   Reply With Quote
Old February 9, 2013, 22:39   #40
LostTemplar
Knight
 
Join Date: Aug 2009
Posts: 670
LostTemplar is on a distinguished road
It is a matter of taste, what to hardcode, you cannot make engine universal. Basically there must be a function, which tells you if a tile is transparent, there are two ways to use this function: call it when tile is checked in LOS function, or call it when tile is changed. I think, that second way will be more effective.

If you have a lot of functions for different kinds of LOS, it still may be faster to call them all for every tile changed. IMHO you will never really have a lot of different LOS types.
LostTemplar is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Pyrel dungeon generation fizzix Variants 50 December 7, 2012 01:32
Pyrel dev log, part 3 Derakon Variants 108 November 12, 2012 23:30
Affixes in Pyrel Magnate Development 0 October 13, 2012 13:53
Pyrel dev log, part 2 Derakon Variants 126 September 11, 2012 23:03
Pyrel dev log Derakon Variants 64 June 8, 2012 11:58


All times are GMT +1. The time now is 23:47.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.