| |
Slightly cold news on page 10! Phlamey breaks the server. |
| |
This is a long thread. Click here to view the threaded list. |
| |
|
Richard Goodwin |
Message #104225, posted by rich at 14:31, 3/9/2007, in reply to message #104221 |
 Dictator for life
Posts: 6828
|
Also: requires traffic lights 
________
 Cheers,
Rich.
|
| |
 [ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #104237, posted by Phlamethrower at 17:04, 3/9/2007, in reply to message #104225 |
 Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Yes. Those should fit in nicely with the method the cars use to plan their movements.
I've also just realised that I can add a simple doppler effect to sounds without much effort, so will probably play with that at some point. |
| |
[ Log in to reply ] |
| |
|
Andrew |
Message #104341, posted by andrew at 18:20, 7/9/2007, in reply to message #104221 |
 Handbag Boi
Posts: 3439
|
How did you string the frames together into an MPEG? |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #104343, posted by Phlamethrower at 19:32, 7/9/2007, in reply to message #104341 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Through a bit of a complicated process 
The frames were just raw dumps of screen data - so the first thing I did was write a program to add a TGA header to each file (since TGA supports the same pixel format the screen data was saved as, and VirtualDub can import TGAs).
The next step was to import the frames into VirtualDub, and save it out as an uncompressed AVI. I also had to choose an approximate framerate to use, since the frames didn't contain any timestamps (and I don't think you can import individually timed frames into VirtualDub anyway)
The final step was to run the AVI through TMPGEnc to convert it to MPEG (since VirtualDub can only save to AVI, and TMPGEnc isn't advanced enough to allow import of individual frames)
I did consider writing some code to save the frames straight into an uncompressed AVI - but lost interest after being unable to find any obvious how-to's on the Internet. I also tried saving the frames as TGAs, but using C file access functions to open a file, write the header, write the data, and then close the file was significantly slower than using OS_File to save a block of memory straight to disc as a new file. (Admittedly I could have stuck with OS_File by rearranging the data in memory a bit, but at that point in time I already had lots of raw frames saved and figured that I might as well just use those)
If I get bored at the weekend I might have another look at the AVI writing and have a go at writing a RISC OS version of FRAPS. But I doubt it would work well at all since IIRC all file writes under RISC OS are blocking, and unless programs provide specific support the code would have to resort to reading the screen data from PCI RAM, which would slow things down further. |
| |
[ Log in to reply ] |
| |
|
Andrew |
Message #104349, posted by andrew at 00:42, 8/9/2007, in reply to message #104343 |
Handbag Boi
Posts: 3439
|
I'm assuming you transferred the frames onto a PC to do that. There was an AVI player for RISC OS - I found it whilst doing a backup this week but can't locate it again. It's called !PlayAVI. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #104369, posted by Phlamethrower at 18:15, 9/9/2007, in reply to message #104349 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
I'm assuming you transferred the frames onto a PC to do that. Yes.
This week(end) I've mainly been working on the AI and physics. I've finally implemented the reverse gear, as well as rewritten the carjacking code to use the new ped AI system - so instead of just teleporting you to the nearest car door it now walks you to it. The only problem is that at the moment there's no way of cancelling it (so if the car you're heading for drives off you'll likely be stuck forever chasing it), and I still haven't written any code to pull drivers out of cars so at the moment you can only steal empty cars.
Apart from a few other tweaks and bugfixes, I decided that it was about time I added a new car, and after a few hours came up with the one visible below. It's based around this concept car, and took about 3 hours to make (including about 1 hour that was lost to Draw crashing inexplicably). Although it still needs more work, I think it proves that the drawfile-to-spritefile converter can be used to make some good-looking cars (especially if I can import an overhead image into Draw and trace the shape )
And in case you're wondering about the red blobs in the screenshot, those are the destinations each AI ped/car is heading to.
[edit]
(a) Car finished
(b) You can now properly carjack people.
(c) The player can now abort carjacking attempts. Hurrah!
[Edited by Phlamethrower at 22:29, 9/9/2007]
[Edited by Phlamethrower at 23:00, 9/9/2007] |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #104376, posted by Loris at 15:47, 10/9/2007, in reply to message #104369 |
 Ha ha, me mine, mwahahahaha
Posts: 1025
|
I don't mean to be rude, but that car looks like an animated football stadium mascot or something.
Hmmm. Perhaps if you changed the colours? |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #104378, posted by Phlamethrower at 17:35, 10/9/2007, in reply to message #104376 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
The new car is shown in three different colour schemes. Or don't you like any of them? 
The big image (screen.png) is a screenshot of the drawfile; it's in red and green so that the converter can easily identify which pixels belong to which recolour block in the palette. There aren't actually any red and green cars in the game
The in-game screenshot is using the two colour schemes shown on the webpage I got the car from; so if you don't like those, blame Honda 
[Edited by Phlamethrower at 18:38, 10/9/2007] |
| |
[ Log in to reply ] |
| |
|
Tony Haines |
Message #104386, posted by Loris at 11:18, 12/9/2007, in reply to message #104378 |
Ha ha, me mine, mwahahahaha
Posts: 1025
|
The new car is shown in three different colour schemes. Or don't you like any of them? I hadn't looked at the screenshot, just the sprite. The other ones look much better; it's just the red and green one.
The big image (screen.png) is a screenshot of the drawfile; it's in red and green so that the converter can easily identify which pixels belong to which recolour block in the palette. There aren't actually any red and green cars in the game Aaaaaah. I see.
The in-game screenshot is using the two colour schemes shown on the webpage I got the car from; so if you don't like those, blame Honda I don't know what it was about the individual one, it just looked like the sort of thing a committee might dream up. But it does look like it - can you see the:goalpost for mouth
lines on the pitch
stadium
googley eyes for anthropomorphising purposes ? |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #104388, posted by Phlamethrower at 15:22, 12/9/2007, in reply to message #104386 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
The new car is shown in three different colour schemes. Or don't you like any of them? I hadn't looked at the screenshot, just the sprite. The other ones look much better; it's just the red and green one.
I'll remember to label the pictures next time
I don't know what it was about the individual one, it just looked like the sort of thing a committee might dream up. But it does look like it - can you see the:goalpost for mouth
lines on the pitch
stadium
googley eyes for anthropomorphising purposes ? Yeah, it does look a bit anthropomorphic and football-themed. But while you're working on it you just need to remember that that's not what it's going to look like when in game
I've been continuing to work on the game for the past couple of nights, and this morning started work on some designs for a much-needed palette editor. Although it's being developed for DeathDawn, the palette editor will probably be useful for any situations that need more advanced palette editing than Paint can provide.
In terms of the next engine release, I'm beginning to aim towards making a release in the next month or two, in time for the 2-year anniversary of when I started coding. The main things I'll be aiming to get done for the release are the palette editor and some tweaked car AI/physics. I'm also continuing to pull together plans for an overhaul of the map generator, to fix the current bugs and allow for new functionality (most importantly the integration needed for mission scripts, and support for hills/bridges/etc.) I'm hoping that this will be done in time for the release as well.
Although there will still be some major engine features missing from this next release (to do with peds, vehicle types, and the map generator) this is likely to be the last "engine test release" before I jump headlong into creating the game content. Unless anyone has any good reasons why I should make more test releases, that is |
| |
[ Log in to reply ] |
| |
|
Andrew |
Message #104390, posted by andrew at 18:40, 12/9/2007, in reply to message #104388 |
Handbag Boi
Posts: 3439
|
The trouble with doing the car that way is it doesn't mesh with the game - the 3D effect isn't there. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #105735, posted by Phlamethrower at 18:42, 18/12/2007, in reply to message #104388 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
I've been continuing to work on the game for the past couple of nights, and this morning started work on some designs for a much-needed palette editor. Although it's being developed for DeathDawn, the palette editor will probably be useful for any situations that need more advanced palette editing than Paint can provide. ...and after about 3 months of nothingness, a few days ago I started work on the palette editor again, to the point where it now compiles and runs, and is almost ready to do some editing. The general idea (as you can see in the screenshot below) is that after loading a spritefile it presents you with a Paint-like view of all the sprites; but instead of editing just one sprite at once, it allows you to edit multiple sprites/palettes at once (except the screenshot doesn't show any sprite editor windows, because I haven't written the code for opening/redrawing them yet). The pane on the right of the palette lists all the sprites that share the same palette as the sprite/palette that you're editing. So if you change an entry in that palette, the corresponding entries in the related sprites will be changed as well. This will extend itself to other operations, such as rearranging palette entries (with the ability to do things like automatically update the pixels in the sprites so that the appearance of the image stays the same). You can add and remove entries from the palette list as you wish, by dragging them in from the main sprite window or removing them via a menu. You'll also be able to import palettes properly (unlike Paint, which just gives an error for 256 colour palettes). You can also import partial palettes (i.e. ones that only change certain palette entries). And although I haven't written any of the code for it, the presence of an undo button means that there should hopefully be undo support at some point (although quite how it will work with one undo button per palette editor I'm not sure)
In terms of the next engine release, I'm beginning to aim towards making a release in the next month or two, in time for the 2-year anniversary of when I started coding. Obviously I've missed that release window now. So in the weeks before/after Christmas I'll probably work towards releasing the palette editor and fontinator (since they're standalone tools), as well as doing some other much-needed updates to my website. |
| |
[ Log in to reply ] |
| |
|
Richard Goodwin |
Message #105791, posted by rich at 18:52, 24/12/2007, in reply to message #105735 |
Dictator for life
Posts: 6828
|
Palette editor you say?
________
Cheers,
Rich.
|
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #105793, posted by Phlamethrower at 19:13, 24/12/2007, in reply to message #105791 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Yes.
I may have tried looking at that before, only to get thwarted by your website not working properly. But now you've reminded me, I guess I'll have to have a proper look |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #105816, posted by Phlamethrower at 17:19, 1/1/2008, in reply to message #105793 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
That editor of yours does seem to do some of what I want, but I don't think it does enough for me to get by just using that. Mainly:
1. I'd still have to drag palettes into Paint to get them applied (which seems to result in "Palette file doesn't match sprite palette" errors most of the time)
2. There's no way of seeing which colours a sprite is using (i.e. hover the mouse over the palette entry and see all corresponding pixels in the sprite highlighted), or vice-versa to quickly see which palette entry a given sprite pixel is using.
3. There's no way of rearranging the palette entries while at the same time rearranging the sprite pixels (so the sprite will look the same when rendered)
4. There doesn't seem to be a way of dragging multiple palette entries around - only single ones.
So in summary: I did not waste 2 days by starting work on my own editor. Hurrah! |
| |
[ Log in to reply ] |
| |
|
Richard Goodwin |
Message #105824, posted by rich at 08:59, 2/1/2008, in reply to message #105816 |
Dictator for life
Posts: 6828
|
So in summary: I did not waste 2 days by starting work on my own editor. Hurrah! Just a day and a half, as you didn't just hack your extras into my pre-existing editor 
I was more pointing at it to show that there's a few extra bits and bobs that might come in handy - using invert and reverse on a few sections makes, for example, a blue palette (chunk) into an orange/brown palette (chunk). Get twice the palettes for half the work. Or something. There might be something you can rip off to save you time.
________
Cheers,
Rich.
|
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #105826, posted by Phlamethrower at 09:19, 2/1/2008, in reply to message #105824 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
So in summary: I did not waste 2 days by starting work on my own editor. Hurrah! Just a day and a half, as you didn't just hack your extras into my pre-existing editor
No - it would have probably taken that half a day to examine your code and work out how it works
I would have also had to mess around adding some code to do memory allocations, since your code seems to rely on static buffers for all the work (and only supports having one document open at once! tsk!)
I was more pointing at it to show that there's a few extra bits and bobs that might come in handy - using invert and reverse on a few sections makes, for example, a blue palette (chunk) into an orange/brown palette (chunk). Get twice the palettes for half the work. Or something. There might be something you can rip off to save you time. Oh.
There may be a few bits of your editor I might use the editor for (or I might steal and put in my own). But I'm not sure what yet. |
| |
[ Log in to reply ] |
| |
|
Richard Goodwin |
Message #105832, posted by rich at 16:42, 2/1/2008, in reply to message #105826 |
Dictator for life
Posts: 6828
|
I would have also had to mess around adding some code to do memory allocations, since your code seems to rely on static buffers for all the work (and only supports having one document open at once! tsk!) As it's written in BASIC, and was the first program I wrote that had redraw code in (with dithering!), I think I did quite well getting it working at all
I also seem to recall that the errors on trying to transfer palettes into Paint from another program are an error in Paint itself. I'm pretty sure using something else - e.g. Photodesk - gives the same error. But then again, it has been several years since I tried it. I think that's why I had to make it simpler to save to RAM disc and manually drag it in
________
Cheers,
Rich.
|
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106078, posted by Phlamethrower at 23:05, 17/1/2008, in reply to message #81718 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Yay!
I, of course, have done nothing  Oi, 
This and this
Still very early days, prototype code outside of Geminus, and the card/NVidia driver seems to have some issues with both displays used together beyond a certain resolution and/or with my funny hacked MDFs (hence the strange aspect ratio; it's 1024x1024 on each screen so that I can use a 2048x1024 for the OS.)
[Edited by adrianl at 21:07, 5/11/2006]
*pokes Adrian*
any progress on that? |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106225, posted by Phlamethrower at 15:17, 26/1/2008, in reply to message #105735 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
So in the weeks before/after Christmas I'll probably work towards releasing the palette editor and fontinator (since they're standalone tools), as well as doing some other much-needed updates to my website. And sure enough, fontinator and Pale are now available for download. Hurrah!
Although there's still quite a few improvements I can make to the palette editor, it's now working well enough and fast enough to be a big help in making cars for DeathDawn. So far I've only had a chance to make one car with it, but due to the extra palette manipulation in the sprites and the way I can combine different deltas ingame the car can come in three different varieties - regular, police, and V8 (with the engine sticking through the bonnet). Two of these variants are shown below, including how they look at night with the better day-night cycle.
No prizes for guessing where the car was copied from (but you can still try if you like). Unfortunately I couldn't find an overhead view to copy, so some bits (particularly the bonnet) may be wrong. But as a further test of the drawfile-to-spritefile converter, and of Pale, (and of the code I had to write to get the flashing police lights working) I'd say it works quite well. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106267, posted by Phlamethrower at 22:23, 29/1/2008, in reply to message #106225 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
On Sunday I started work on the new/improved map generator, and somewhat quicker than I was expecting I now have a version that (almost) paints roads properly, and (almost) supports hills. I say "almost" for both of those because there's still one rare bug with the roads, and the hills (apart from not being fully implemented) are making me realise that my current code/data structures don't work very well for painting sloping roads. Luckily I think a few simple changes are all that are needed to make the whole road/path/intersection painting a lot more simple and robust. Once the hill code is sorted out I'll also be able to add train tracks, traffic lights, and support for mission-specific buildings. At some point it should also support rivers, boulders, and other obstructions - but for the moment I'm ignoring those and getting cities working properly.
If everything goes to plan, this new generator will be able to do everything the game needs.
[edit]
Predictably, my changes to tidy up the code have now broken everything. Even the simple task of setting the height of each point along a slope
[Edited by Phlamethrower at 00:15, 30/1/2008] |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106298, posted by Phlamethrower at 20:02, 3/2/2008, in reply to message #106267 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Small updatey thing:
The hill painting code is almost complete. A lot of time was spent fixing bugs, which means that I now have a better idea of what does and doesn't work with the new/improved generator. In particular, a lot of the problems seem to stem from the fact that the generator relies on things being done in a certain order - but when dealing with multiple map layers, things aren't always done in the order the generator expects, so problems occur where the two layers join up. So I'm trying to decide what the best course of action is to deal with that problem, preferably without adding things which make the map generator slower or use significantly more memory. There are still some bugs to fix (overlapping parallel roads) and features to add (train tracks, traffic lights), so I'll probably try doing those before making any decisions about restructuring the generator again.
I've also had a mess around with some other things, like selecting some fonts for potential use in the game (and updating the font code to support variable-width fonts). Except that one of the fonts I've chosen seems to be dodgy and causes a font manager SWI I'm calling in my font tool to crash when reading the character bounding boxes. Strangely the font seems to work fine when used in other programs, but unless I can think of another way of reading the bounding boxes I'll probably have to add some code for a brute-force approach.
I've also had a go at vectorising the long-neglected playpen.iswe.net logo for use in the game. But I'm not telling you how or why it's getting used
Once a few more things on the map generator have been done I think I'll do another 'test' release, since a lot of stuff has changed since the last one. The car physics still isn't fantastic, but since I'm probably going to be the one who tweaks and balances all the cars I don't think it really matters if no one else gets to see the finished code until the game is finished.
If I stay focused then I think there's a good chance that I'll finally get the game engine finished this year. But whether the game itself gets finished this year is a different matter entirely, since I've got no idea how long it will take to get all the final art/sound assets together, or how long it will take to write, test and tweak the car stats and missions. |
| |
[ Log in to reply ] |
| |
|
VinceH |
Message #106300, posted by VincceH at 22:51, 3/2/2008, in reply to message #106298 |
 Lowering the tone since the dawn of time
Posts: 1600
|
've also had a go at vectorising the long-neglected playpen.iswe.net logo for use in the game. But I'm not telling you how or why it's getting used Hmmm.
Sounds like you're thinking of incorporating advertising in the game |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106341, posted by Phlamethrower at 23:57, 5/2/2008, in reply to message #106300 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
've also had a go at vectorising the long-neglected playpen.iswe.net logo for use in the game. But I'm not telling you how or why it's getting used Hmmm.
Sounds like you're thinking of incorporating advertising in the game
Only for fictional organisa... oh.
Perhaps I'd better go with my backup plan of The Playpen Bar & Grill(e?). (And remove the shadow on the black text so you can actually see what it says).
But, the more significant thing than the playpen making an appearance, is that I've now written the code for custom buildings and the mission script integration for the map generator. So now mission scripts can request that certain buildings appear in the map, and in return get told the location of the building and any points listed in the definition file.
The only downside to the custom building code is that writing block-by-block building definitions by hand is quite hard work, so I may have to work on that a bit so that it requires less typing and head-scratching.
[Edited by Phlamethrower at 23:59, 5/2/2008] |
| |
[ Log in to reply ] |
| |
|
VinceH |
Message #106345, posted by VincceH at 09:15, 6/2/2008, in reply to message #106341 |
Lowering the tone since the dawn of time
Posts: 1600
|
Sounds like you're thinking of incorporating advertising in the game Only for fictional organisa... oh.
Perhaps I'd better go with my backup plan of The Playpen Bar & Grill(e?).
And just for fun, especially with all the cheap and nasty free or low cost hosts out there, you could come up with matching websites for the organisations...
(And remove the shadow on the black text so you can actually see what it says). Yeah, that text is a bit messy. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106346, posted by Phlamethrower at 09:33, 6/2/2008, in reply to message #106345 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
And just for fun, especially with all the cheap and nasty free or low cost hosts out there, you could come up with matching websites for the organisations... Cheap and nasty? Free or low cost? Hello!
</rich> |
| |
[ Log in to reply ] |
| |
|
VinceH |
Message #106347, posted by VincceH at 13:54, 6/2/2008, in reply to message #106346 |
Lowering the tone since the dawn of time
Posts: 1600
|
And just for fun, especially with all the cheap and nasty free or low cost hosts out there, you could come up with matching websites for the organisations... Cheap and nasty? Free or low cost? Hello!
</rich>
Oh yeah, silly, forgetful me. |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106402, posted by Phlamethrower at 00:23, 11/2/2008, in reply to message #106347 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
Apart from a few other little jobs, this weekend I've been focusing on trains. A train carriage and some simple train track tiles have been drawn and converted/imported. I've added code to the game for managing the waypoint based train tracks. But the main focus was on writing the track planning code for the map generator, which is now working in an almost-kinda way, as you should be able to see in the screenshot below. The green stripey things are meant to be the stations, and the yellow/green/blue rails are the train tracks. Obviously there are still some bugs like missing track sections and it thinking the top-right station exit goes to the left instead of to the right, but the code is mostly doing what it should be. (It's also putting the tracks through buildings, but that's just because I've got the track collision checks turned off).
At the moment I'm using an A* algorithm to try and plan the tracks, but the large number of possible places where new track sections can be placed (4 corners in 2 directions and 6 combinations of straight sections) seems to be causing a bit of a problem with memory usage. Turning on the track collision checking will hopefully make things better, but I don't think it will have enough of an effect over long distances. A different, more direct algorithm might be the solution, even if it results in less than perfect output.
[edit]
And after a bug fix for the missing sections, and turning on the collision detection, and fudging the generator so it produces less alternate paths (I've restricted it to just the smallest corners, and to only produce sloping track if it must change height in order to reach its destination), the algorithm is now 'working', as can be seen in another screenshot below. (The tracks leading off to the right connect up to a third station). Unfortunately, even though the longest section generated only contains 19 track nodes, it still needed to generate over 46,000 nodes to find that solution. So if I don't want the algorithm to eat tons of memory (46,000 nodes is about 3MB), or take ages to generate, I'll still probably have to look into using a different algorithm.
[Edited by Phlamethrower at 00:52, 11/2/2008] |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #106408, posted by Phlamethrower at 22:16, 11/2/2008, in reply to message #106402 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
As you'd expect, I've been having a play with the track algorithm some more.
I've swapped the small track corners with the largest ones, so that they're actually big enough for the train to get around. I've also tweaked the code that places slopes, so that it's allowed to place upward slopes only if it's currently at the highest point of the track. This allows it to put bridges over other road/track sections if needed, as well as over small buildings. However I've also got a fairly strict height limiter, which prevents it from going more than one block higher than the highest of the two points it's trying to connect. I might be able to remove this limit at some point, or relax it a little. I've also added code to get rid of useless track paths once all the tracks have been generated, so that you don't end up with trains driving down tracks that don't go anywhere.
But more importantly, I think I've realised what the main flaw is with the algorithm - it has no way of quickly determining whether the destination is walled-in and cannot be reached. Determining whether the start point is walled-in is quite easy, because it will soon run out of places to put track nodes and abort the algorithm. But for a regular A* algorithm to determine whether the destination is walled-in would require it to search every possible location - which is the point at which the algorithm takes both a massive amount of time and memory to execute. If a path can be found then it will usually find it within a few seconds, using an acceptable amount of memory; but if it can't be found then it could take minutes or hours to work out that it can't reach the target, and possibly use so much memory that it runs out (There's scope for about a million nodes to be generated before it works out the target can't be reached - which would currently use up around 60MB of RAM).
There are really two solutions to this problem - place a time/memory limit on the algorithm to stop it from running if it looks like it isn't going to reach the target, or switch to an algorithm that is able to search from both the start and destination nodes at the same time - aka bidirectional search. Bidirectional search looks like a sensible choice, and one that will be fairly easy to implement in my current framework, so that's what I'll be starting with. Once it's implemented however I may also add some time/memory constraints, to stop the algorithm in the unlikely event that there's a giant brick wall exactly between the two track nodes I'm trying to join together.
The only problem with bi-directional search is that it can't really be used for the intercity train tracks - tracks that just lead from a station off to an arbitrary point on the edge of the map. Luckily however those types of track should have enough goal states that a traditional A* algorithm can be used for them - although I'll also back it up with time/memory constraints to be on the safe side.
Also another problem that won't be solved by the bidirectional search is the problem where one track inadvertently blocks off a station exit, stopping another track from forming altogether. To solve this I'd either have to restrict tracks from being placed within a certain radius of open nodes, or write some horribly complex algorithm that tries to connect all the tracks at once. So I suspect I'll be going with the former rather than the latter. |
| |
[ Log in to reply ] |
| |
|
VinceH |
Message #106409, posted by VincceH at 22:35, 11/2/2008, in reply to message #106408 |
Lowering the tone since the dawn of time
Posts: 1600
|
ISTM that the railway tracks might have been better generated *before* the rest of the map. Lay the tracks, then map/build a city around them.
But with all the work already done, that's probably not such a practical approach now. |
| |
[ Log in to reply ] |
| |
| Pages (22): |< <
20
> >|
|
