Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Variants

Reply
 
Thread Tools Display Modes
Old April 7, 2013, 04:24   #41
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,923
Derakon is on a distinguished road
Quote:
Originally Posted by mtadd View Post
My contribution to last year's discussion of LOS / FOV was this link on FOV using recursive shadowcasting. The article describes the algorithm nicely, as well as provides and implementation in python at the end.
Thanks; I'll have to check that out when I get a chance. For now I'm working on a copy of the "precise permissive field of view" algorithm described here -- mostly because d_m handed me a copy of the code that worked already. Of course I'll be trying to design things so that we can swap in different LOS/FOV algorithms with minimal pain. I don't have any sacred cows in this particular area; I just want something that basically works so I can start working on player knowledge.
Derakon is offline   Reply With Quote
Old April 7, 2013, 05:48   #42
mtadd
Rookie
 
Join Date: Nov 2011
Posts: 24
mtadd is on a distinguished road
Derakon,

I'll take a look at your implementation of A* soon. In the meantime, I was wondering if you ever read this article on Dijkstra Maps by the developer of Brogue? Its an interesting technique of creating gradients using a modified Dijkstra graph search through the passable portions of the map with differing intial conditions to assist in pathfinding, autoexploring, and mob AI.

Last edited by mtadd; April 7, 2013 at 16:41.
mtadd is offline   Reply With Quote
Old April 7, 2013, 06:18   #43
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,923
Derakon is on a distinguished road
I haven't seen it, no. Add another thing to my list of stuff to check out.

In general I do embarrassingly little research on most of these algorithms, instead relying mostly on what I learned as an undergrad and what I've heard about / used in the past in my years as a hobbyist game developer and general professional software developer. I won't remotely claim that this is the right way to do things, but working on Pyrel is a hobby for me so I'm going to do what I enjoy, and sometimes that's redesigning or reimplementing the wheel.
Derakon is offline   Reply With Quote
Old April 8, 2013, 23:34   #44
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,923
Derakon is on a distinguished road
Okay, player field-of-view is implemented!



Here we can see the debug town, complete with an alleyway holding the Phial and the Arkenstone. The best thing about this is that those artifacts are guarded by a filthy street urchin, which the player cannot see. Yes, the player's information is incomplete for the first time! This involves having the player maintain a mental copy of the game map which is updated each turn based on what's in their field of view. As squares leave their FOV, all "transient" entities are removed from that mental copy, thus removing things like creatures but leaving terrain, items, etc. behind.

One point of amusement here is that the field of view is square -- 20 steps in each direction, including diagonally. It looks kind of funny but is the Right Thing to do (so long as diagonal movement costs the same as orthogonal movement, anyway).

One thing I haven't done yet is keep track of cells that the player has seen but that are currently empty, hence why all non-visible empty cells aren't displayed at all rather than being displayed as dim '.'s. That shouldn't be difficult though.

Oh, yes -- I ought to have mentioned this earlier. Between the pathfinding and the field of view work, I've decided it makes the most sense to just have Pyrel include Numpy as a dependency rather than try to do all these array operations etc. ourselves. Numpy is reliably efficient and makes dealing with large arrays of numbers in Python much more pleasant (compared to working with lists of lists, for example). It is one more thing to install though.

EDIT: checked out the dungeons, fixing a few bugs in dungeon generation in the process. Looks like some of this code didn't get very thoroughly tested; oh well. Anyway, turns out A* pathfinding isn't the best idea for monsters in actual dungeons -- I was looking at about .5s/step. Guess I'll need to switch to something like heat maps (a.k.a. the "Dijkstra Maps" mtadd linked earlier) so there's less work for each individual creature to do when deciding where to go next.

Oh well. The A* pathfinding system works, and it could still come in handy for one-off effects. I could imagine e.g. a spell that draws a glowing line on the ground to lead the player to some objective, for example; sure, a heat map would do the same thing, but A* has the advantage in one-offs of not needing to examine the entire map.

Last edited by Derakon; April 9, 2013 at 02:53.
Derakon is offline   Reply With Quote
Old April 9, 2013, 09:44   #45
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 Derakon View Post
One point of amusement here is that the field of view is square -- 20 steps in each direction, including diagonally. It looks kind of funny but is the Right Thing to do (so long as diagonal movement costs the same as orthogonal movement, anyway).
Thank you for the bait - I've been meaning to air this for a while. To me, diagonal movement costing the same is Just Wrong. There's no truly compelling reason - the strongest one is visceral ugh, the next is that it makes something that looks like a square actually function as a circle, which just jars. Neither is game-breaking: most roguelikes have done this for years with no particular ill effects. But I like the idea that Pyrel isn't bound by these tropes, and could actually implement proper movement costs. Yes, this would mean that if you move diagonally a monster could move horizontally and then attack you before you move again. But that feels intuitively correct, rather than diagonals being handy escape routes.
Quote:
Oh, yes -- I ought to have mentioned this earlier. Between the pathfinding and the field of view work, I've decided it makes the most sense to just have Pyrel include Numpy as a dependency rather than try to do all these array operations etc. ourselves. Numpy is reliably efficient and makes dealing with large arrays of numbers in Python much more pleasant (compared to working with lists of lists, for example). It is one more thing to install though.
Installing deps is trivial for Linux folks but horrible for Windows users. Is there some way we can bundle Numpy with the Pyrel setup for Windows? Worth investing time in an msi?
Quote:
EDIT: checked out the dungeons, fixing a few bugs in dungeon generation in the process. Looks like some of this code didn't get very thoroughly tested; oh well.
There are two types of tests. There are code tests (unit tests, end-to-end tests, whatever they're called), and playing tests. The former require much more professionalism and discipline than your contributors have, and the latter are almost impossible at such an early stage of development - there are doubtless hundreds of bugs in my item code which haven't been found yet because items haven't been picked up, wielded, used, damaged, destroyed etc. etc. The only bugs I've been able to test for are the ones in generation - and I had to write a chunk of wizmode even to do that. So I don't think it's surprising or reprehensible that the dungeon code, by the same token, isn't fully tested.
__________________
"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 April 9, 2013, 15:04   #46
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 3,002
fizzix is on a distinguished road
Quote:
Originally Posted by Derakon View Post
EDIT: checked out the dungeons, fixing a few bugs in dungeon generation in the process. Looks like some of this code didn't get very thoroughly tested; oh well. Anyway, turns out A* pathfinding isn't the best idea for monsters in actual dungeons -- I was looking at about .5s/step. Guess I'll need to switch to something like heat maps (a.k.a. the "Dijkstra Maps" mtadd linked earlier) so there's less work for each individual creature to do when deciding where to go next.
mea culpa!

We should discuss moving some of the dungeon calculations over to numpy now that it's available.
fizzix is offline   Reply With Quote
Old April 9, 2013, 16:14   #47
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,923
Derakon is on a distinguished road
The bugs I found were actually due to the massive refactor that Kinematics did -- things like a factory still checking for nameSuffix, or trying to check isArtifact instead of looking in the item's categories. I mostly just meant that line as a reminder to other devs to try generating a few levels before assuming your changes are done and working.

Re: numpy, it's about as easy to install as it gets, even on Windows. There are binary installers for basically every Python/OS combination, so once you have Python 2.7 installed, you just go to their download page, and find either the 32- or 64-bit Python2.7 Numpy installer, download it, and run it. That's it.

Pyrel itself will eventually need to be its own little standalone Python environment, just so that players don't need to manually install everything themselves. My expectation is that newbie devs will be able to do a fair amount of hacking on Pyrel without having to install a "real" Python environment, but it's really the right thing for them to do in the long run. IMO for now at least we should limit ourselves to having an installation guide that walks users through installing everything they need.

As for sight radius, I disagree with Magnate. My main problem with making diagonal movement more expensive is precisely that basically no other grid-based game both a) allows diagonal movement at all, and b) makes it more expensive timewise than orthogonal movement. Breaking with tradition means significant unintuitiveness here, which, due to its nature, is going to lead to deaths through getting double-turned. Is it weird that diagonal movement is cheaper? Sure. But that boat sailed long, long ago. It's just one of those things that you have to deal with in the roguelike genre (and indeed in basically every top-down tile-based game).
Derakon is offline   Reply With Quote
Old April 9, 2013, 16:23   #48
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 Derakon View Post
Is it weird that diagonal movement is cheaper? Sure. But that boat sailed long, long ago. It's just one of those things that you have to deal with in the roguelike genre (and indeed in basically every top-down tile-based game).
Except the entire Civ series, which charged 1.5 movement points for diagonal moves before switching to hexes for Civ V.

I suspect there are a number of other top-down tile-based games that do this too, it is unlikely that Civ is the only one.

Never mind.
__________________
"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 April 19, 2013, 05:13   #49
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,923
Derakon is on a distinguished road
Hey Pyrel contributors, we need to choose a license. I always assumed Pyrel was operating under GPLv2, but I admit I never specified that explicitly. Is this acceptable to everyone else? Any other preferred licenses? Once we decide this I'll add a LICENSE.txt to the root level of the repository so others will easily be able to figure out how we operate.
Derakon is offline   Reply With Quote
Old April 19, 2013, 06:59   #50
mtadd
Rookie
 
Join Date: Nov 2011
Posts: 24
mtadd is on a distinguished road
I authorize all code contributed by me to Pyrel to be licensed via GPLv2.

Matthew Tadd
mtadd 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 dev log, part 4 Magnate Variants 116 March 11, 2013 19:53
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 22:38.


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